Бессвязное встраивание

В топологической теории графов , математической дисциплине, бессвязное вложение неориентированного графа — это вложение графа в трехмерное евклидово пространство таким образом, что никакие два цикла графа не связаны между собой. Плоское вложение — это вложение, обладающее тем свойством, что каждый цикл является границей топологического диска , внутренняя часть которого не пересекается с графом. Бессвязный встраиваемый граф — это граф, имеющий бессвязное или плоское вложение; эти графы образуют трехмерный аналог планарных графов . Кроме того, внутренне связанный граф — это граф, который не имеет встраивания без связей.

Плоские вложения автоматически становятся бессвязными, но не наоборот. Полный граф K ₆ , граф Петерсена и другие пять графов семейства Петерсена не имеют вложений без связей. Каждый минор графа бессвязно встраиваемого графа снова является бессвязно встраиваемым, как и любой граф, который может быть получен из бессвязно встраиваемого графа с помощью YΔ- и ΔY-преобразований . бессвязно встраиваемых графов являются семейства Петерсенов графы Запрещенными минорами . и включить плоские графы и вершинные графы . Их можно распознать и построить для них плоское вложение в O ( n ² ) .

Определения

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

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

Связующее число двух замкнутых кривых в трехмерном пространстве является топологическим инвариантом кривых: это число, определенное из кривых любым из нескольких эквивалентных способов, которое не меняется, если кривые перемещаются непрерывно, не проходя через каждую из них. другой. Вариант числа зацепления, используемый для определения бесзвенных вложений графов, находится путем проецирования вложения на плоскость и подсчета количества пересечений проецируемого вложения, при которых первая кривая проходит через вторую по модулю 2. Проекция должна быть «правильной», что означает, что никакие две вершины не проектируются в одну и ту же точку, ни одна вершина не выступает внутрь ребра, и в каждой точке проекции, где проекции двух ребер пересекаются, они пересекаются трансверсально ; с этим ограничением любые две проекции приводят к одному и тому же числу связей.Число связывания при разрыве связи равно нулю, и, следовательно, если пара кривых имеет ненулевое число связывания, две кривые должны быть связаны. Однако есть примеры кривых, которые связаны, но имеют нулевое число связей, например, связь Уайтхеда .

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

В некоторых случаях граф может быть вложен в пространство таким образом, что для каждого цикла в графе можно найти круг, ограниченный этим циклом, который не пересекает какой-либо другой элемент графа. В этом случае цикл должен быть отвязан от всех остальных непересекающихся с ним циклов в графе. Вложение называется плоским, если каждый цикл таким образом ограничивает диск. Плоское вложение обязательно является бессвязным, но могут существовать бессвязные вложения, которые не являются плоскими: например, если G — граф, образованный двумя непересекающимися циклами, и он вложен для формирования ссылки Уайтхеда, то вложение является бессвязным, но не плоским. .

Граф называется внутренне связанным, если независимо от того, как он вложен, вложение всегда связано. Хотя бессвязные и плоские вложения — это не одно и то же, графы с бессвязными вложениями такие же, как и графы с плоскими вложениями.

Примеры и контрпримеры

Семья Петерсен .

Как показал Сакс (1983) , каждый из семи графов семейства Петерсена неразрывно связан: независимо от того, как каждый из этих графов вложен в пространство, они имеют два цикла, связанных друг с другом. Эти графы включают полный граф K ₆ , граф Петерсена , граф , образованный удалением ребра из полного двудольного графа K _4,4 , и полный трехдольный граф K _3,3,1 .

Каждый планарный граф имеет плоское и бессвязное вложение: просто вставьте граф в плоскость, а плоскость — в пространство. Если граф планарен, это единственный способ встроить его в пространство плоско и без связей: каждое плоское вложение можно непрерывно деформировать, чтобы оно лежало на плоской плоскости. И наоборот, каждый непланарный бессвязный граф имеет множество бессвязных вложений.

Вершинный граф . Если плоская часть графа вложена на плоскую плоскость в пространстве, а вершинная вершина расположена над плоскостью и соединена с ней отрезками прямых, то полученное вложение будет плоским.

Вершинный граф , образованный добавлением единственной вершины к планарному графу, также имеет плоское и бессвязное вложение: встроить плоскую часть графа в плоскость, поместить вершину над плоскостью и провести ребра от вершины к ее вершине. соседи как отрезки прямой. Любая замкнутая кривая внутри плоскости ограничивает диск ниже плоскости, который не проходит через какой-либо другой элемент графика, а любая замкнутая кривая, проходящая через вершину, ограничивает диск над плоскостью, который не проходит через какой-либо другой элемент графика.

Если граф имеет бессвязное или плоское вложение, то модификация графа путем разделения или разделения его ребер, добавления или удаления нескольких ребер между одной и той же парой точек и выполнения YΔ- и ΔY-преобразований , которые заменяют вершину третьей степени на вершину треугольник, соединяющий трех своих соседей, или наоборот, сохраняют плоскостность и бессвязность. В частности, в кубическом планарном графе (в котором все вершины имеют ровно три соседа, например в кубе) можно сделать дубликаты любого независимого набора вершин, выполнив YΔ-преобразование, добавив несколько копий полученного треугольника. ребра, а затем выполняя обратные ΔY-преобразования.

Характеристика и признание

Если граф G имеет бесзвенное или плоское вложение, то каждый минор графа G (граф, образованный сжатием ребер и удалением ребер и вершин) также имеет бесзвенное или плоское вложение. Удаление не может нарушить плоскостность вложения, а сжатие можно выполнить, оставив одну конечную точку сжатого ребра на месте и перенаправив все ребра, инцидентные другой конечной точке, вдоль пути сжатого ребра. Следовательно, по теореме Робертсона-Сеймура бессвязно встраиваемые графы имеют характеристику запрещенного графа как графы, которые не содержат ни одного из конечного набора миноров.

Набор запрещенных миноров для бессвязно встраиваемых графов был определен Саксом (1983) : все семь графов семейства Петерсена являются минорно-минимальными внутренне связанными графами. Однако Саксу не удалось доказать, что это были единственные минимальные связанные графы, и это наконец удалось Робертсону , Сеймуру и Томасу (1995) .

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

Проблема эффективной проверки того, является ли данное вложение плоским или бессвязным, была поставлена ​​Робертсоном, Сеймуром и Томасом (1993a) . Она остается нерешенной и по сложности эквивалентна проблеме развязывания узлов — проблеме проверки того, развязана ли отдельная кривая в пространстве. Известно, что проверка незавязанности (и, следовательно, также проверка бессвязности вложения) осуществляется в NP, но не известно, что она NP-полна .

Родственные семейства графов

Графы с малым инвариантом Колена де Вердьера

Инвариант графа Колена де Вердьера — это целое число, определенное для любого графа с использованием алгебраической теории графов . Графы с графом Колена де Вердьера, инвариантным не более µ, для любой фиксированной константы µ образуют минорно-замкнутое семейство, и первые несколько из них хорошо известны: графы с µ ≤ 1 представляют собой линейные леса (непересекающиеся объединения пути), графы с ц < 2 являются внешнепланарными графами , а графы с ц < 3 являются планарными графами . Как предположили Робертсон, Сеймур и Томас (1993a) и доказали Ловас и Шрейвер (1998) , графы с µ ≤ 4 являются в точности бессвязными встраиваемыми графами.

Апекс-графики

Вершинный граф без связей, который не сокращается по YΔY.

Плоские графы и вершинные графы вложимы без зацеплений, как и графы, полученные YΔ- и ΔY-преобразованиями из этих графов. - Приводимые графы YΔY это графы, которые можно свести к одной вершине с помощью YΔ- и ΔY-преобразований, удаления изолированных вершин и вершин первой степени и сжатия вершин второй степени; они также минорно-замкнуты и включают все плоские графы. Однако существуют графы без связей, которые не сокращаются по YΔY, такие как вершинный граф, образованный путем соединения вершинной вершины с каждой вершиной третьей степени ромбического додекаэдра . Также существуют графы без связей, которые нельзя преобразовать в вершинный граф с помощью YΔ- и ΔY-преобразований, удаления изолированных вершин и вершин первой степени и сжатия вершин второй степени: например, десятивершинный коронный граф имеет бессвязное встраивание, но его нельзя преобразовать в вершинный граф таким образом.

Бесузловые графы

Замкнутая кривая, образующая трилистник , простейший нетривиальный узел.

С концепцией вложения без связей связана концепция вложения без узлов, то есть вложения графа таким образом, что ни один из его простых циклов не образует нетривиальный узел . Графы, не имеющие безузловых вложений (т. е. внутренне завязанные ), включают K ₇ и K _3,3,1,1 . Однако существуют также минимальные запрещенные миноры для безузлового вложения, которые не образуются (как эти два графа) путем добавления одной вершины к внутренне связанному графу, но их список неизвестен.

Семейства графов также можно определить по наличию или отсутствию более сложных узлов и связей в их вложениях. или путем бесзвенного вложения в трехмерные многообразия, отличные от евклидова пространства. Флапан, Наими и Поммерсхайм (2001) определяют вложение графа как тройную связность, если существуют три цикла, ни один из которых не может быть отделен от двух других; они показывают, что K ₉ не является по своей сути тройной связью, а K ₁₀ - есть. В более общем смысле, можно определить n -связное вложение для любого n как вложение, содержащее n -компонентную связь, которую нельзя разделить топологической сферой на две отдельные части; минорно-минимальные графы, которые внутренне являются n -связными, известны для всех n .

История

Вопрос о том, имеет ли K6 _{сообществе} бесзвенное или плоское вложение, был поставлен в исследователей топологии в начале 1970-х годов Боте (1973) . Бесзвенные вложения были доведены до сведения сообщества графов теории Хорстом Саксом ( 1983 ), который поставил несколько связанных проблем, включая проблему нахождения запрещенной графовой характеристики графов с бесзвенными и плоскими вложениями; Сакс показал, что семь графов семейства Петерсена (включая K ₆ ) не имеют таких вложений. Как заметили Нешетржил и Томас (1985) , бессвязно встраиваемые графы замкнуты относительно миноров графа следует , из чего по теореме Робертсона-Сеймура , что характеризация запрещенного графа существует. Доказательство существования конечного множества графов препятствий не приводит к явному описанию этого множества запрещенных миноров, но из результатов Сакса следует, что семь графов семейства Петерсена принадлежат этому множеству. Эти проблемы были окончательно решены Робертсоном, Сеймуром и Томасом (1995). , который показал, что семь графов семейства Петерсенов являются единственными минимальными запрещенными минорами для этих графов. Следовательно, и бессвязно встраиваемые графы, и плоские встраиваемые графы представляют собой один и тот же набор графов, и оба такие же, как графы, не имеющие минора семейства Петерсена.

Сакс (1983) также просил ограничить количество ребер и хроматическое число встраиваемых графов без связей. Число ребер в n -вершинном бесзвенном графе не превосходит 4 n − 10: максимальные вершинные графы с n > 4 имеют ровно столько ребер, и Мадер (1968) доказал согласованную верхнюю оценку для более общего класса K ₆ графов без миноров . Нешетржил и Томас (1985) заметили, что вопрос Сакса о хроматическом числе может быть решен путем доказательства гипотезы Хадвигера о том, что любой k -хроматический граф имеет в качестве минора полный граф с k -вершиной. Доказательство Робертсона, Сеймура и Томаса (1993c) случая k = 6 гипотезы Хадвигера достаточно, чтобы решить вопрос Сакса: графы без связей можно раскрасить не более чем пятью цветами, поскольку любой 6-хроматический граф содержит K ₆ второстепенный и не является бессвязным, и существуют бессвязные графы, такие как K ₅ , для которых требуется пять цветов. Из теоремы о снарке следует, что каждый кубический бессвязно встраиваемый граф раскрашивается в 3 ребра .

Бессвязные вложения начали изучаться в исследовательском сообществе алгоритмов в конце 1980-х годов в работах Fellows & Langston (1988) и Motwani, Raghunathan & Saran (1988) . Алгоритмически проблема распознавания бессвязных и плоских встраиваемых графов была решена после того, как была доказана запрещенная минорная характеристика: алгоритм Робертсона и Сеймура (1995) можно использовать для проверки за полиномиальное время , содержит ли данный граф какой-либо из семи запрещенных миноров. Этот метод не создает бессвязные или плоские вложения, если они существуют, но алгоритм, который создает вложение, был разработан ван дер Холстом (2009) , а более эффективный алгоритм с линейным временем был найден Каварабаяши, Крейцером и Мохаром (2010) .

Последний вопрос Сакса (1983) о возможности аналога теоремы Фари для бесзвенных графов, похоже, не получил ответа: когда из существования бесзвенного или плоского вложения с изогнутыми или кусочно-линейными ребрами следует существование бесзвенного или кусочно-линейного вложения? плоское вложение, в котором ребра представляют собой отрезки прямых линий ?

См. также

• Узлы и графики

Ссылки

• Бёме, Томас (1990), «О пространственных представлениях графов», в книге Бодендика, Райнера (ред.), Современные методы в теории графов: в честь профессора доктора. Клаус Вагнер , Мангейм: Библиографический институт, научное издательство, стр. 151–167, ISBN.  978-3-411-14301-6 . Цитируется Робертсоном , Сеймуром и Томасом (1993a) .
• Боте, Х.-Г. (1973), «Проблема P855», Colloquium Mathematicum , 28 : 163, New Scottish Book, Задача 876, 20.5.1972 . Цитируется Саксом (1983) .
• Боулин, Гарри; Фуази, Джоэл (2004), «Некоторые новые внутренне 3-связные графы» (PDF) , Журнал теории узлов и ее разветвлений , 13 (8): 1021–1028, doi : 10.1142/S0218216504003652 .
• Конвей, Джон Х .; Гордон, Кэмерон МакА. (1983), «Узлы и связи в пространственных графах», Journal of Graph Theory , 7 (4): 445–453, doi : 10.1002/jgt.3190070410 .
• Товарищи, Майкл Р .; Лэнгстон, Майкл А. (1988), «Неконструктивные инструменты для доказательства разрешимости за полиномиальное время», Journal of the ACM , 35 (3): 727–739, doi : 10.1145/44483.44491 .
• Флапан, Эрика ; Ховардс, Хью; Лоуренс, Дон; Меллор, Блейк (2006), «Внутреннее связывание и завязывание узлов графов в произвольных трехмерных многообразиях», Алгебраическая и геометрическая топология , 6 : 1025–1035, arXiv : math/0508004 , doi : 10.2140/agt.2006.6.1025 .
• Флапан, Эрика ; Наими, Рамин; Поммершайм, Джеймс (2001), «Полные графы с тройной связью» (PDF) , Топология и ее приложения , 115 (2): 239–246, doi : 10.1016/S0166-8641(00)00064-X .
• Флапан, Эрика ; Поммершайм, Джеймс; Фуази, Джоэл; Наими, Рамин (2001), «Внутренне n-связанные графы», Журнал теории узлов и ее разветвлений , 10 (8): 1143–1154, doi : 10.1142/S0218216501001360 .
• Флеминг, Томас; Дизль, Александр (2005), «Неразрывно связанные графы и даже связующее число», Algebraic & Geometric Topology , 5 : 1419–1432, arXiv : math/0511133 , doi : 10.2140/agt.2005.5.1419 .
• Фуази, Джоэл (2002), «Графы с внутренними узлами», Journal of Graph Theory , 39 (3): 178–187, doi : 10.1002/jgt.10017 .
• Фуази, Джоэл (2003), «Недавно признанный внутренне завязанный граф», Journal of Graph Theory , 43 (3): 199–209, doi : 10.1002/jgt.10114 .
• Хасс, Джоэл ; Лагариас, Джеффри С .; Пиппенджер, Николас (1999), «Вычислительная сложность задач узлов и связей», Журнал ACM , 46 (2): 185–211, arXiv : math/9807016 , doi : 10.1145/301970.301971 .
• ван дер Хольст, Хейн (2009), «Алгоритм с полиномиальным временем для поиска бессвязного вложения графа», Журнал комбинаторной теории, серия B , 99 (2): 512–530, doi : 10.1016/j.jctb. 2008.10.002 .
• Каварабаяси, Кеничи ; Крейцер, Стефан; Мохар, Боян (2010), «Бесзвенные и плоские вложения в трехмерном пространстве и проблема узлов», Proc. Симпозиум ACM по вычислительной геометрии (SoCG '10) , стр. 97–106, doi : 10.1145/1810959.1810975 .
• Ловас, Ласло ; Шрийвер, Александр (1998), «Теорема Борсука для антиподальных связей и спектральная характеристика бессвязно встраиваемых графов», Proceedings of the American Mathematical Society , 126 (5): 1275–1285, doi : 10.1090/S0002-9939-98- 04244-0 .
• Мадер, В. (1968), «Теоремы о гомоморфии графов», Mathematical Annals , 178 (2): 154–168, doi : 10.1007/BF01350657 .
• Мотвани, Раджив ; Рагунатан, Арвинд; Саран, Хузур (1988), «Конструктивные результаты из миноров графа: вложения без связей», Proc. 29-й симпозиум IEEE по основам информатики (FOCS '88) , стр. 398–409, номер документа : 10.1109/SFCS.1988.21956 .
• Нешетржил, Ярослав ; Томас, Робин (1985), «Заметки о пространственном представлении графов» , Commentationes Mathematicae Universitatis Carolinae , 26 (4): 655–659, заархивировано из оригинала 18 июля 2011 г.
• Робертсон, Нил ; Сеймур, Пол (1995), «Незначительные графы. XIII. Проблема непересекающихся путей», Журнал комбинаторной теории, серия B , 63 (1): 65–110, doi : 10.1006/jctb.1995.1006 .
• Робертсон, Нил ; Сеймур, Пол ; Томас, Робин (1993a), «Обзор бессвязных вложений», Робертсон, Нил ; Сеймур, Пол (ред.), Теория структуры графов: Proc. Совместная летняя исследовательская конференция AMS – IMS – SIAM по минорным графам (PDF) , Contemporary Mathematics, vol. 147, Американское математическое общество, стр. 125–136 .
• Робертсон, Нил ; Сеймур, Полиция ; Томас, Робин (1993b), «Бесзвенные вложения графов в трехмерное пространство», Бюллетень Американского математического общества , 28 (1): 84–89, arXiv : math/9301216 , doi : 10.1090/S0273-0979-1993- 00335-5 , МР   1164063 .
• Робертсон, Нил ; Сеймур, Полиция ; Томас, Робин (1995), «Гипотеза Сакса о бесзвенном вложении», Журнал комбинаторной теории, серия B , 64 (2): 185–227, doi : 10.1006/jctb.1995.1032 .
• Робертсон, Нил ; Сеймур, Пол ; Томас, Робин (1993c), «Гипотеза Хадвигера для PDF ₍ графов, свободных от K6» ) , Combinatorica , 13 (3): 279–361, doi : 10.1007/BF01202354 .
• Сакс, Хорст (1983), «О пространственном аналоге теоремы Куратовского о плоских графах - открытая проблема», в Горовецкий, М.; Кеннеди, JW; Сысло М.М. (ред.), Теория графов: материалы конференции, состоявшейся в Лагуве, Польша, 10–13 февраля 1981 г. , Конспекты лекций по математике, том. 1018, Springer-Verlag, стр. 230–241, doi : 10.1007/BFb0071633 .
• Саран, Хузур (1989), Конструктивные результаты в минорных графах: бессвязные вложения , доктор философии. диссертация, Калифорнийский университет, Беркли .
• Трумпер, Клаус (1992), Разложение матроида (PDF) , Academic Press, стр. 100–101 .

Дальнейшее чтение

• Рамирес Альфонсин, Х.Л. (2005), «Узлы и связи в пространственных графах: обзор», Discrete Mathematics , 302 (1–3): 225–242, doi : 10.1016/j.disc.2004.07.035 .