Незачеплене вкладення графа

Незачеплене вкладення графа — вкладення неорієнтованого графа в евклідів простір, за якого жодні два цикли графа не мають ненульового коефіцієнта зачеплення. Плоске вкладення — вкладення, в якому будь-який цикл є межею топологічного круга, внутрішність якого не зачеплена з графом. Граф, що вкладається без зачеплень, — граф, що має незачеплене або плоске вкладення. Ці графи утворюють тривимірний аналог планарних графів[1]. Напроти, суттєво зачеплений граф — це граф, який не має незачепленого вкладення.

Плоскі вкладення автоматично не мають зачеплень, але не навпаки[2]. Повний граф ${\displaystyle K_{6}}$, граф Петерсена та інші п'ять графів із петерсенового сімейства графів не мають незачеплених вкладень[1]. Графи, що допускають незачеплене вкладення, замкнені за мінорами графа[3] і перетвореннями Y-Δ[2]. Вони мають графи петерсенового сімейства забороненими мінорами [4] і включають планарні графи та вершинні графи[2]. Графи можна розпізнати (а плоске вкладення — побудувати) за лінійний час [5].

Визначення

Дві зачеплені криві, що утворюють зачеплення Гопфа

Кажуть, що дві неперетинні криві в евклідовому просторі не зачеплені, якщо існує безперервний рух кривих, який перетворює їх у два незачеплені копланарні кола без проходження однієї кривої через іншу або через себе. Якщо такого безперервного руху немає, кажуть, що криві зачеплені. Зачеплення Гопфа, утворене двома колами, які проходять через диск, натягнутий на ці кола, дає найпростіший приклад пари зачеплених кривих, але криві можуть бути зачеплені значно складніше. Якщо криві не зачеплені, можна знайти (топологічний) диск у просторі, обмежений першою кривою, який не перетинається з другого. І тому, якщо такий диск існує, криві не зачеплені.

Коефіцієнт зачеплення двох замкнутих кривих у тривимірному просторі є топологічним інваріантом кривої — це число, визначене для кривих одним з еквівалентних способів, яке не змінюється, якщо рухати криві в просторі безперервно без перетинання одна одної або себе. Коефіцієнт зачеплення знаходять, спроєктувавши вкладення на площину та підрахувавши певним чином числа проходів першої кривої над другою (зі знаком +1 або -1 залежно від напрямку проходу). Проєкція має бути «правильною», що означає, що жодні дві вершини не проєктуються в одну точку, жодна вершина не проєктується всередину ребра і в будь-якій точці проєкції, де ребра перетинаються, вони перетинаються трансверсально. За таких обмежень будь-яка проєкція дає той самий коефіцієнт зачеплення. Коефіцієнт зачеплення незачеплених кривих дорівнює нулю, а тому, якщо пара кривих має ненульовий коефіцієнт зачеплення, дві криві мають бути зачепленими. Однак є приклади зачеплених кривих, що мають нульовий коефіцієнт зачеплення, наприклад, зачеплення Вайтгеда.

Вкладення графа в тривимірний простір складається з відображення вершин графа в точки простору і відображень ребер у криві, так що кожна кінцева точка ребра відображається в кінцеву точку відповідної кривої і криві, що відповідають двом різним ребрам, не перетинаються (хіба що в спільних кінцевих точках). Будь-який скінченний граф має скінченне (можливо експоненціальне) число різних простих циклів, і, якщо граф укладено в тривимірний простір, кожен такий цикл утворює просту замкнуту криву. Можна обчислити коефіцієнт зачеплення кожної пари кривих, що не перетинаються, утворених таким чином. Якщо всі пари циклів мають нульовий коефіцієнт зачеплення, кажуть, що вкладення є незачепленим[6][1][2].

У деяких випадках граф можна вкласти в простір так, що для кожного циклу в графі можна знайти диск, обмежений цим циклом, який не перетинає інших елементів графа. У цьому випадку цикл має бути не зачепленим з іншими циклами графа, що не перетинають його. Кажуть, що вкладення плоске, якщо будь-який цикл обмежує диск у такий спосіб[2]. Аналогічне визначення «хорошого вкладення» наведено в статті Мотвані, Рагунатана та Сарана (Motwani, Raghunathan, Saran, 1988. Див. також Saran, (1989) та Böhme, (1990).</ref>. Плоске вкладення обов'язково є незачепленим, але можуть бути незачеплені вкладення, які не є плоскими. Наприклад, якщо G — граф, утворений двома роздільними циклами, і при вкладенні утворюється зачеплення Вайтгеда, вкладення є незачепленим, але не плоским.

Кажуть, що граф суттєво зачеплений, якщо за будь-якого вкладення виходить зачеплене вкладення. Хоча незачеплене і плоске вкладення не те ж саме, графи, які мають незачеплені вкладення, виявляються тими ж графами, що й графи, які мають плоскі вкладення[7].

Приклади та контрприклади

Петерсенове сімейство графів.

Як показав Сакс[1], усі сім графів петерсенового сімейства істотно зачеплені, і не має значення, як ці графи вкладені в простір: за будь-якого вкладення вони мають два зачеплених цикли. Ці графи включають повний граф ${\displaystyle K_{6}}$, граф Петерсена, граф, утворений видаленням ребра з повного двочасткового графа ${\displaystyle K_{4,4}}$, і повний тричастковий граф ${\displaystyle K_{3,3,1}}$.

Будь-який планарний граф має плоске і незачеплене вкладення — просто вкладаємо граф у площину, що міститься в (тривимірному) просторі. Якщо граф планарний, це єдиний спосіб укладання графа плоско і незачеплено — будь-яке плоске вкладення можна неперервно деформувати у вкладення на площині. І навпаки, будь-який непланарний незачеплений граф має множинні незачеплені вкладення[2].

Верхівковий граф. Якщо планарну частину графа вкладено в площину, розташовану в просторі, верхівка графа (вершина, що порушує планарність), поміщається над площиною і з'єднується прямими відрізками, і одержане вкладення є плоским.

Верхівковий граф, утворений додаванням однієї вершини до планарного графа, також має плоске і незачеплене вкладення — вкладаємо планарну частину графа на площину, поміщаємо верхівку графа (вершина, що порушує планарність) над площиною, а потім проводимо ребра з верхівки в суміжні їй вершини у вигляді відрізків. Будь-яка замкнута крива на площині обмежує диск, який не проходить через інший елемент графа, а будь-яка замкнута крива через верхівку обмежує диск над площиною, який не проходить через будь-який інший елемент графа[2].

Якщо граф має незачеплене або плоске вкладення, то модифікація графа поділом або об'єднанням його ребер, додаванням або видаленням кратних ребер між парою вершин або проведенням Y-Δ-перетворень, за яких вершина степеня три замінюється трикутником, що з'єднує три сусіди, або навпаки, приводить до збереження існування плоского або незачепленого вкладення[2]. Зокрема, в кубічному планарному графі (в якому всі вершини мають рівно три сусіди, як у куба) можна зробити копії будь-якої незалежної множини вершин, здійснивши Y-Δ-перетворення, додавши кратні копії ребер в отриманих трикутниках, а потім здійснивши зворотне Δ-Y-перетворення.

Характеризація і розпізнавання

Якщо граф ${\displaystyle G}$ має незачеплене або плоске вкладення, то будь-який мінор графа ${\displaystyle G}$ (граф, утворений стягуванням ребер і видаленням ребер і вершин) також має незачеплене або плоске вкладення. Видалення не може зруйнувати можливість незачепленого або плоского вкладення, а стягування можна здійснити, залишивши одну кінцеву точку стягуваного ребра на місці і перемкнувши всі ребра, інцидентні протилежній вершині. Таким чином, за теоремою Робертсона — Сеймура, графи, що мають незачеплене вкладення, мають характеризацію забороненими графами як графи, що не містять будь-якого зі скінченного набору мінорів[3].

Множину заборонених мінорів для графів, що допускають незачеплене вкладення, виявив Сакс[1] — сім графів петерсенового сімейства є мінорно мінімальними істотно зачепленими графами. Однак Сакс не зміг довести, що тільки ці графи є мінорно мінімальними зачепленими графами, і це зробили Робертсон, Сеймур і Томас[4].

Характеризація забороненими мінорами графів, які допускають незачеплене вкладення, веде до алгоритму їх розпізнавання з поліноміальним часом роботи, але при цьому цей алгоритм не будує дійсного вкладення. Каравабайші, Крейцер і Мохар[5] описали алгоритм з лінійним часом роботи, який перевіряє, чи вкладаний граф незачеплено, і, якщо вкладаний, будує плоске вкладення графа. Їхній алгоритм знаходить великі планарні підграфи всередині заданого графа, такі, що, якщо існує незачеплене вкладення, вони представляють планарне вкладення підграфа. Повторно спрощуючи граф, коли такий підграф знайдено, вони зводять задачу до задачі, в якій решта графа обмежена деревною шириною, і з цього моменту задачу можна розв'язати за допомогою динамічного програмування.

Задачу ефективної перевірки, чи є задане вкладення плоским або незачепленим, поставили Робертсон, Сеймур і Томас[2]. Задача залишається нерозв'язаною і за складністю еквівалентна задачі розв'язування вузла, задачі перевірки, чи є крива в просторі незавузленою[5]. Відомо, що перевірка незавузленості (а отже, й незачепленого вкладення) належить до класу NP, але невідомо, чи належить вона до класу NP-повних задач[8].

Пов'язані сімейства графів

Інваріант Колен де Вердьєра — це число, визначене для будь-якого графа на основі алгебричної теорії графів. Граф з інваріантом Колен де Вердьєра, що не перевершує μ, для будь-якої фіксованої сталої μ утворює замкнуте за мінорами сімейство, і кілька перших таких сімейств добре відомі: графи з μ ≤ 1 — це лінійні ліси (незв'язне об'єднання шляхів), графи з μ ≤ 2 — зовніпланарні графи, а графи з μ ≤ 3 — планарні графи. Як припустили Робертсон, Сеймур і Томас[2] і довели Ловас і Шрайвер[9], графами з μ ≤ 4 точно є графи з незачепленим вкладенням.

Незачеплений вершинний граф, нескоротний перетворенням YΔY.

Планарні графи і вершинні графи допускають незачеплене вкладення, як і графи, одержувані Y-Δ перетвореннями з них[2]. YΔY-скоротні графи — це графи, які можна звести до однієї вершини перетворенням Y-Δ, видаленням ізольованих і завислих вершин (вершин степеня 1) і заміною дуг при вершині степеня два однією дугою. Ці графи також замкнуті за мінорами. Однак існують незачеплені YΔY-нескоротні графи, такі як верхівковий граф, утворений з'єднанням верхівки (вершини, що порушує планарність) із усіма вершинами степеня три ромбододекаедра[10]. Існують також незачеплені графи, які не можна перетворити за допомогою Y-Δ-перетворень, видаленням ізольованих і завислих вершин і заміною дуг при вершині зі степенем два однією дугою на вершинний граф. Наприклад, корона з десятьма вершинами має незачеплене вкладення, але її не можна перетворити на вершинний граф у зазначений спосіб[2].

З поняттям незачепленого вкладення пов'язане поняття незавузленого вкладення. Це таке вкладення графа, що ніякої простий цикл не утворює нетривіального вузла. До графів, що не мають незавузленого вкладення, належать K₇ і K_3,3,1,1[6][11]. Однак існують мінімальні заборонені мінори для незавузлених вкладень, які не утворені (на відміну від зазначених двох графів) доданням однієї вершини до істотно зачепленого графа[12].

Можна визначити сімейства графів за наявністю або відсутністю в їх вкладенні складніших вузлів і зачеплень[3][13], або за незачепленим вкладенням у тривимірний многовид^[en], відмінний від евклідового простору[14]. Флапан, Наїмі і Поммершейм[15] визначили вкладення графа як тричі зачеплене, якщо існують три цикли, жоден з яких не можна відокремити від двох інших. Вони показали, що K₉ не тричі істотно зачеплений, а K₁₀ зачеплений[16]. Загальніше, можна визначити n-зачеплене вкладення для будь-якого ${\displaystyle n}$ як вкладення, що містить ${\displaystyle n}$-компонентне зачеплення, яке не можна розділити топологічною сферою на дві окремі частини. Мінорно мінімальні істотно ${\displaystyle n}$-зачеплені графи відомі для всіх ${\displaystyle n}$[17].

Історія

Питання, чи має ${\displaystyle K_{6}}$ зачеплене або плоске вкладення, поставив на початку 1970-х у топологічній дослідницькій спільноті Боте[18]. До незачепленого вкладення привернув увагу теоретиків графів Сакс[1], який запропонував кілька пов'язаних задач, зокрема, задачу пошуку характеризації забороненими графами графів із незачепленим або плоским вкладенням. Він показав, що сім графів петерсенового сімейства (включно з ${\displaystyle K_{6}}$) не мають таких вкладень. Як помітили Нешетріл і Томас[3], графи, що допускають незацеплене вкладення, замкнуті за мінорами графа, звідки за теоремою Робертсона — Сеймура випливає, що характеризація забороненими графами існує. Доведення існування скінченного числа перешкоджальних графів не веде до явного опису цієї множини заборонених мінорів, але з результатів Сакса випливає, що сім графів петерсенового сімейства належать до множини. Ці задачі остаточно розв'язали Робертсон, Сеймур і Томас[4][7], які показали, що ці сім графів петерсенового сімейства є єдиними мінімальними забороненими мінорами для таких графів. Таким чином, незачеплено вкладені графи і плоско вкладені графи є однією й тією ж множиною графів і обидва сімейства можна визначити як графи, що не містять елементів сімейства Петерсена як мінорів.

Сакс[1] також поставив питання про межі числа ребер і хроматичного числа вкладаних без зачеплення графів. Число ребер у вкладаному без зачеплення графі з ${\displaystyle n}$ вершинами не перевищує ${\displaystyle 4n-10}$ — максимальні верхівкові графи з ${\displaystyle n>4}$ мають рівно таке число ребер[1], а Мадер[19] довів правильність верхньої межі для загальнішого класу вільних від K₆ мінорів графів. 1985 року показано, що питання Сакса про хроматичне число було б вирішене, якби було доведено гіпотезу Хадвігера, що будь-який ${\displaystyle k}$-хроматичний граф має в як мінор повний граф з ${\displaystyle k}$ вершинами[3]. Доведення Робертсона, Сеймура і Томаса[20] випадку ${\displaystyle k=6}$ гіпотези Хадвігера достатньо для вирішення питання Сакса — графи без зачеплень можна розфарбувати максимум п'ятьма кольорами, оскільки будь-який 6-хроматичний граф містить мінор ${\displaystyle K_{6}}$ і не є незачепленим, і існують незачеплені графи, такі як ${\displaystyle K_{5}}$, що вимагають п'яти кольорів. Із теореми про снарки випливає, що будь-який кубічний вкладений без зачеплення граф є реберно розфарбовуваним у 3 кольори.

Вивчення вкладень без зачеплень почалося наприкінці 1980-х років під час дослідження алгоритмів[21][22]. Алгоритмічно задачу розпізнавання вкладених без зачеплень і плоско вкладених графів розв'язано, коли було доведено характеризацію забороненими мінорами — алгоритм Робертсона і Сеймура[23] можна використати для перевірки за поліноміальний час, чи містить заданий граф будь-який із семи заборонених мінорів[24]. Цей метод не будує незачепленого або плоского вкладення, якщо воно існує, але ван дер Голст (Hein van der Holst) запропонував алгоритм, який будує вкладення[25], а пізніше знайдено ефективніший алгоритм, що працює за лінійний час[5].

На останнє питання Сакса[1] про можливість аналогії теореми Фарі для незачеплених графів відповіді поки немає. Питання ставиться так: коли існування незачепленого або плоского вкладення з кривими або кусково-лінійними ребрами тягне існування незачепленого або плоского вкладення, в якому ребра є відрізками?

Примітки

1. Sachs, 1983.
2. Robertson, Seymour, Thomas, 1993a.
3. Nešetřil, Thomas, 1985.
4. Robertson, Seymour, Thomas, 1995.
5. Kawarabayashi, Kreutzer, Mohar, 2010.
6. Conway, Gordon, 1983.
7. Robertson, Seymour, Thomas, 1993b.
8. Hass, Lagarias, Pippenger, 1999.
9. Lovász, Schrijver, 1998.
10. Truemper, 1992.
11. Foisy, 2002.
12. Foisy, 2003.
13. Fleming, Diesl, 2005.
14. Flapan, Howards, Lawrence, Mellor, 2006.
15. Flapan, Naimi, Pommersheim, 2001.
16. Інші приклади не тричі зачеплених графів див. у Bowlin, Foisy, 2004.
17. Flapan, Pommersheim, Foisy, Naimi, 2001.
18. Bothe, 1973.
19. Mader, 1968.
20. Robertson, Seymour, Thomas, 1993c.
21. Fellows, Langston, 1988.
22. Motwani, Raghunathan, Saran, 1988.
23. Robertson, Seymour, 1995.
24. Застосовність алгоритму Робертсона — Сеймура до цієї задачі помітили Феллоус і Лангстон (Fellows, Langston, 1988).
25. van der Holst, 2009.

Література

• Thomas Böhme. Contemporary Methods in Graph Theory: In honor of Prof. Dr. Klaus Wagner / Rainer Bodendieck. — Mannheim : Bibliographisches Institut, Wissenschaftsverlag, 1990. — С. 151–167. — ISBN 978-3-411-14301-6.. Як процитировано в книзі Робертсона, Сеймура, Томаса (Robertson, Seymour, Thomas, 1993a).
• H.-G. Bothe. Problem P855 // Colloquium Mathematicum. — 1973. — Т. 28. — С. 163. — (New Scottish Book,).. Як процитировано в книзі Сакса (Sachs, (1983)).
• Garry Bowlin, Joel Foisy. Some new intrinsically 3-linked graphs // Journal of Knot Theory and its Ramifications. — 2004. — Т. 13, вип. 8. — С. 1021–1028. — DOI:10.1142/S0218216504003652.
• John H. Conway, Cameron McA. Gordon. Knots and links in spatial graphs // Journal of Graph Theory. — 1983. — Т. 7, вип. 4. — С. 445–453. — DOI:10.1002/jgt.3190070410.
• Michael R. Fellows, Michael A. Langston. Nonconstructive tools for proving polynomial-time decidability // Journal of the ACM. — 1988. — Т. 35, вип. 3. — С. 727–739. — DOI:10.1145/44483.44491.
• Erica Flapan, Hugh Howards, Don Lawrence, Blake Mellor. Intrinsic linking and knotting of graphs in arbitrary 3–manifolds // Algebraic & Geometric Topology. — 2006. — Т. 6. — С. 1025–1035. — arXiv:math/0508004. — DOI:10.2140/agt.2006.6.1025.
• Erica Flapan, Ramin Naimi, James Pommersheim. Intrinsically triple linked complete graphs // Topology and its Applications. — 2001. — Т. 115, вип. 2. — С. 239–246. — DOI:10.1016/S0166-8641(00)00064-X.
• Erica Flapan, James Pommersheim, Joel Foisy, Ramin Naimi. Intrinsically n-linked graphs // Journal of Knot Theory and Its Ramifications. — 2001. — Т. 10, вип. 8. — С. 1143–1154. — DOI:10.1142/S0218216501001360..
• Thomas Fleming, Alexander Diesl. Intrinsically linked graphs and even linking number // Algebraic & Geometric Topology. — 2005. — Т. 5. — С. 1419–1432. — arXiv:math/0511133. — DOI:10.2140/agt.2005.5.1419.
• Joel Foisy. Intrinsically knotted graphs // Journal of Graph Theory. — 2002. — Т. 39, вип. 3. — С. 178–187. — DOI:10.1002/jgt.10017.
• Joel Foisy. A newly recognized intrinsically knotted graph // Journal of Graph Theory. — 2003. — Т. 43, вип. 3. — С. 199–209. — DOI:10.1002/jgt.10114.
• Joel Hass, Jeffrey C. Lagarias, Nicholas Pippenger. The computational complexity of knot and link problems // Journal of the ACM. — 1999. — Т. 46, вип. 2. — С. 185–211. — arXiv:math/9807016. — DOI:10.1145/301970.301971.
• Hein van der Holst. A polynomial-time algorithm to find a linkless embedding of a graph // Journal of Combinatorial Theory, Series B. — 2009. — Т. 99, вип. 2. — С. 512–530. — DOI:10.1016/j.jctb.2008.10.002.
• Ken-ichi Kawarabayashi, Stephan Kreutzer, Bojan Mohar. Proc. ACM Symposium on Computational Geometry (SoCG '10). — 2010. — С. 97–106. — DOI:10.1145/1810959.1810975.
• László Lovász, Alexander Schrijver. A Borsuk theorem for antipodal links and a spectral characterization of linklessly embeddable graphs // Proceedings of the American Mathematical Society. — 1998. — Т. 126, вип. 5. — С. 1275–1285. — DOI:10.1090/S0002-9939-98-04244-0.
• W. Mader. Homomorphiesätze für Graphen // Mathematische Annalen. — 1968. — Т. 178, вип. 2. — С. 154–168. — DOI:10.1007/BF01350657.
• Rajeev Motwani, Arvind Raghunathan, Huzur Saran. Proc. 29th IEEE Symposium on Foundations of Computer Science (FOCS '88). — 1988. — С. 398–409. — DOI:10.1109/SFCS.1988.21956.
• Jaroslav Nešetřil, Robin Thomas. A note on spatial representation of graphs // Commentationes Mathematicae Universitatis Carolinae. — 1985. — Т. 26, вип. 4. — С. 655–659. Архівовано з джерела 18 липня 2011.
• Neil Robertson, Paul Seymour. Graph Minors. XIII. The disjoint paths problem // Journal of Combinatorial Theory, Series B. — 1995. — Т. 63, вип. 1. — С. 65–110. — DOI:10.1006/jctb.1995.1006.
• Neil Robertson, Paul Seymour, Robin Thomas. Graph Structure Theory: Proc. AMS–IMS–SIAM Joint Summer Research Conference on Graph Minors. — American Mathematical Society, 1993a. — Т. 147. — С. 125–136. — (Contemporary Mathematics)
• Neil Robertson, Paul Seymour, Robin Thomas. Linkless embeddings of graphs in 3-space // Bulletin of the American Mathematical Society. — 1993b. — Т. 28, вип. 1. — С. 84–89. — arXiv:math/9301216. — DOI:10.1090/S0273-0979-1993-00335-5..
• Neil Robertson, Paul Seymour, Robin Thomas. Sachs' linkless embedding conjecture // Journal of Combinatorial Theory, Series B. — 1995. — Т. 64, вип. 2. — С. 185–227. — DOI:10.1006/jctb.1995.1032..
• Neil Robertson, Paul Seymour, Robin Thomas. Hadwiger's conjecture for K₆-free graphs // Combinatorica. — 1993c. — Т. 13, вип. 3. — С. 279–361. — DOI:10.1007/BF01202354..
• Horst Sachs. On a spatial analogue of Kuratowski's Theorem on planar graphs – an open problem / M. Horowiecki, J. W. Kennedy, M. M. Sysło. — Graph Theory: Proceedings of a Conference held in Łagów, Poland, February 10–13, 1981. — Springer-Verlag, 1983. — Т. 1018. — С. 230–241. — (Lecture Notes in Mathematics) — DOI:10.1007/BFb0071633..
• Huzur Saran. Constructive Results in Graph Minors: Linkless Embeddings. — University of California, Berkeley, 1989. — (Ph.D. thesis).
• Klaus Truemper. Matroid Decomposition. — Academic Press, 1992. — С. 100–101..
• J. L. Ramírez Alfonsín. Knots and links in spatial graphs: a survey // Discrete Mathematics. — 2005. — Т. 302, вип. 1–3. — С. 225–242. — DOI:10.1016/j.disc.2004.07.035.