Незацепленное вложение графа

Незацепленное вложение графа — вложение неориентированного графа в евклидово пространство, при котором никакие два цикла графа не имеют ненулевой коэффициент зацепления. Плоское вложение — вложение, при котором любой цикл является границей топологического круга, внутренность которого не зацеплена с графом. Вложимый без зацеплений граф — граф, имеющий незацепленное или плоское вложение. Эти графы образуют трёхмерный аналог планарным графам[1]. В противоположность, существенно зацепленный граф — это граф, не имеющий незацепленного вложения.

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

Определения

Две зацепленные кривые, образующие зацепление Хопфа.

Говорят, что две непересекающиеся кривые в евклидовом пространстве не зацеплены, если существует непрерывное движение кривых, которое преобразует их в две незацепленные копланарные окружности без прохождения одной кривой через другую или через себя. Если такого непрерывного движения нет, говорят, что кривые зацеплены. Зацепление Хопфа, образованное двумя окружностями, которые проходят через диск, натянутый на эти окружности, даёт простейший пример пары зацепленных кривых, но кривые могут быть зацеплены существенно более сложным образом. Если кривые не зацеплены, можно найти (топологический) диск в пространстве, ограниченный первой кривой и не пересекающийся со второй. И обратно, если такой диск существует, кривые не зацеплены.

Коэффициент зацепления двух замкнутых кривых в трёхмерном пространстве является топологическим инвариантом кривой — это число, определённое для кривых одним из эквивалентных способов, которое не меняется, если двигать кривые в пространстве непрерывно без пересечения друг друга или себя. Коэффициент зацепления находится путём проектирования вложения на плоскость и подсчёта определённым образом числа проходов первой кривой над второй (со знаком +1 или −1 в зависимости от направления прохода). Проекция должна быть «правильной», что означает, что никакие две вершины не проецируются в одну точку, никакая вершина не проецируется внутрь ребра и в любой точке проекции, где рёбра пересекаются, они пересекаются трансверсально. При таких ограничениях любая проекция ведёт к одному и тому же коэффициенту зацепления. Коэффициент зацепления незацепленных кривых равен нулю, а поэтому, если пара кривых имеет ненулевой коэффициент зацепления, две кривые должны быть зацеплены. Однако существуют примеры зацепленных кривых, имеющих нулевой коэффициент зацепления, например, зацепление Уайтхеда.

Вложение графа в трёхмерное пространство состоит из отображения вершин графа в точки пространства и отображений рёбер в кривые, так что каждая конечная точка ребра отображается в конечную точку соответствующей кривой и кривые, соответствующие двум различным рёбрам, не пересекаются (разве что в общих конечных точках). Любой конечный граф имеет конечное (возможно экспоненциальное) число различных простых циклов, и, если граф вложен в трёхмерное пространство, каждый такой цикл образует простую замкнутую кривую. Можно вычислить коэффициент зацепления каждой непересекающейся пары кривых, образованных таким образом. Если все пары циклов имеют нулевой коэффициент зацепления, говорят, что вложение является незацепленным[6][1][2].

В некоторых случаях граф может быть вложен в пространство таким образом, что для каждого цикла в графе можно найти диск, ограниченный этим циклом, который не пересекает другие элементы графа. В этом случае цикл должен быть не зацеплен с другими циклами графа, не пересекающими его. Говорят, что вложение плоское, если любой цикл ограничивает диск описанным образом[2]. Аналогично определение "хорошего вложения " приведено в статье Мотвани, Рагунатана и Сарана Motwani, Raghunathan, Saran, 1988. См. также Saran (1989) harvtxt error: якоря не существует: CITEREFSaran1989 (помощь) и Böhme (1990) harvtxt error: якоря не существует: CITEREFBöhme1990 (помощь). Плоское вложение обязательно является незацепленным, но могут существовать незацепленные вложения, не являющиеся плоскими. Например, если 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], или по незацепленному вложению в трёхмерное многообразие, отличному от евклидова пространства[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]. Этот метод не строит незацепленное или плоское вложение, если оно существует, но алгоритм, строящий вложение[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.. Как процитировано в книге Сакса (Sachs (1983) harvtxt error: якоря не существует: CITEREFSachs1983 (помощь)).
• 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. — doi:10.2140/agt.2006.6.1025. — arXiv:math/0508004.
• 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. — doi:10.2140/agt.2005.5.1419. — arXiv:math/0511133.
• 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. — doi:10.1145/301970.301971. — arXiv:math/9807016.
• 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 / Neil Robertson, Paul Seymour. — 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. — doi:10.1090/S0273-0979-1993-00335-5. — arXiv:math/9301216..
• 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.