Бесконечное вложение - Linkless embedding

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

Плоские вложения автоматически не содержат ссылок, но не наоборот. Полный граф K ₆ , то граф Петерсена , а остальные пять графиков в семье Петерсен не linkless вложений. Каждый второстепенный граф бесконечно встраиваемого графа снова является встраиваемым без ссылок, как и любой граф, к которому можно получить доступ из бесконечно встраиваемого графа с помощью преобразования Y-Δ . Встраиваемые без ссылок графы имеют графы семейства Петерсена в качестве запрещенных миноров и включают в себя планарные графы и вершинные графы . Их можно распознать и построить для них плоское вложение в . ${\ Displaystyle О (п ^ {2})}$

Определения

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Связанные семейства графов

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

Беззвенный вершинный граф, который не является YΔY-приводимым.

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

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

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

История

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

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

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

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

Смотрите также

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

Заметки

Рекомендации

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