Русская Википедия:Незацепленное вложение графа
Незацепленное вложение графа — вложение неориентированного графа в евклидово пространство, при котором никакие два цикла графа не имеют ненулевой коэффициент зацепления. Плоское вложение — вложение, при котором любой цикл является границей топологического круга, внутренность которого не зацеплена с графом. Вложимый без зацеплений граф — граф, имеющий незацепленное или плоское вложение. Эти графы образуют трёхмерный аналог планарным графамШаблон:Sfn. В противоположность, существенно зацепленный граф — это граф, не имеющий незацепленного вложения.
Плоские вложения автоматически не имеют зацеплений, но не наоборотШаблон:Sfn. Полный граф <math>K_6</math>, граф Петерсена и другие пять графов из петерсенова семейства графов не имеют незацепленных вложенийШаблон:Sfn. Допускающие незацепленное вложение графы замкнуты по минорам графаШаблон:Sfn и преобразованиям Y-ΔШаблон:Sfn. Эти графы имеют графы петерсенова семейства в качестве запрещённых миноровШаблон:Sfn и включают планарные графы и вершинные графыШаблон:Sfn. Графы могут быть распознаны (а плоское вложение может быть построено) за линейное времяШаблон:Sfn.
Определения
Говорят, что две непересекающиеся кривые в евклидовом пространстве не зацеплены, если существует непрерывное движение кривых, которое преобразует их в две незацепленные копланарные окружности без прохождения одной кривой через другую или через себя. Если такого непрерывного движения нет, говорят, что кривые зацеплены. Зацепление Хопфа, образованное двумя окружностями, которые проходят через диск, натянутый на эти окружности, даёт простейший пример пары зацепленных кривых, но кривые могут быть зацеплены существенно более сложным образом. Если кривые не зацеплены, можно найти (топологический) диск в пространстве, ограниченный первой кривой и не пересекающийся со второй. И обратно, если такой диск существует, кривые не зацеплены.
Коэффициент зацепления двух замкнутых кривых в трёхмерном пространстве является топологическим инвариантом кривой — это число, определённое для кривых одним из эквивалентных способов, которое не меняется, если двигать кривые в пространстве непрерывно без пересечения друг друга или себя. Коэффициент зацепления находится путём проектирования вложения на плоскость и подсчёта определённым образом числа проходов первой кривой над второй (со знаком +1 или −1 в зависимости от направления прохода). Проекция должна быть «правильной», что означает, что никакие две вершины не проецируются в одну точку, никакая вершина не проецируется внутрь ребра и в любой точке проекции, где рёбра пересекаются, они пересекаются трансверсально. При таких ограничениях любая проекция ведёт к одному и тому же коэффициенту зацепления. Коэффициент зацепления незацепленных кривых равен нулю, а поэтому, если пара кривых имеет ненулевой коэффициент зацепления, две кривые должны быть зацеплены. Однако существуют примеры зацепленных кривых, имеющих нулевой коэффициент зацепления, например, зацепление Уайтхеда.
Вложение графа в трёхмерное пространство состоит из отображения вершин графа в точки пространства и отображений рёбер в кривые, так что каждая конечная точка ребра отображается в конечную точку соответствующей кривой и кривые, соответствующие двум различным рёбрам, не пересекаются (разве что в общих конечных точках). Любой конечный граф имеет конечное (возможно экспоненциальное) число различных простых циклов, и, если граф вложен в трёхмерное пространство, каждый такой цикл образует простую замкнутую кривую. Можно вычислить коэффициент зацепления каждой непересекающейся пары кривых, образованных таким образом. Если все пары циклов имеют нулевой коэффициент зацепления, говорят, что вложение является незацепленнымШаблон:SfnШаблон:SfnШаблон:Sfn.
В некоторых случаях граф может быть вложен в пространство таким образом, что для каждого цикла в графе можно найти диск, ограниченный этим циклом, который не пересекает другие элементы графа. В этом случае цикл должен быть не зацеплен с другими циклами графа, не пересекающими его. Говорят, что вложение плоское, если любой цикл ограничивает диск описанным образомШаблон:Sfn. Аналогично определение "хорошего вложения " приведено в статье Мотвани, Рагунатана и Сарана Шаблон:Sfn0. См. также Шаблон:Harvtxt и Шаблон:Harvtxt. Плоское вложение обязательно является незацепленным, но могут существовать незацепленные вложения, не являющиеся плоскими. Например, если G является графом, образованным двумя раздельными циклами, и при вложении получается зацепление Уайтхэда, вложение является незацепленным, но не плоским.
Говорят, что граф существенно зацеплен, если при любом вложении получается всегда зацепленное вложение. Хотя незацепленное и плоское вложения не то же самое, графы, имеющие незацепленные вложения оказываются теми же графами, что и графы, имеющие плоские вложенияШаблон:Sfn.
Примеры и контрпримеры
Как показал СаксШаблон:Sfn, все семь графов петерсенова семейства существенно зацеплены, и не имеет значения, как эти графы вложены в пространство, при любом вложении они имеют два зацепленных цикла. Эти графы включают полный граф <math>K_6</math>, граф Петерсена, граф, образованный удалением ребра из полного двудольного графа <math>K_{4,4}</math>, и полный трёхдольный граф <math>K_{3,3,1}</math>.
Любой планарный граф имеет плоское и незацепленное вложение — просто вкладываем граф в плоскость, находящуюся в (трёхмерном) пространстве. Если граф планарен, это единственный путь вложения графа плоско и незацепленно — любое плоское вложение можно непрерывно деформировать во вложение на плоскости. И наоборот, любой непланарный незацепленный граф имеет множественные незацепленные вложенияШаблон:Sfn.
Верхушечный граф, образованный добавлением одной вершины к планарному графу, также имеет плоское и нецеплённое вложение — вкладываем планарную часть графа на плоскость, помещаем верхушку графа (нарушающую планарность вершину) над плоскостью, а затем проводим рёбра из верхушки в смежные ей вершины в виде отрезков. Любая замкнутая кривая на плоскости ограничивает диск, который не проходит через другой элемент графа, а любая замкнутая кривая через верхушку ограничивает диск над плоскостью, который не проходит через любой другой элемент графаШаблон:Sfn.
Если граф имеет незацепленное или плоское вложение, то модификация графа путём разделения или объединения его рёбер, добавления или удаления кратных рёбер между парой вершин или проведения Y-Δ-преобразований, при котором вершина степени три заменяется треугольником, соединяющим три соседа, или обратно, приводит к сохранению существования плоского или незацепленного вложенияШаблон:Sfn. В частности, в кубическом планарном графе (в котором все вершины имеют в точности три соседа, как у куба) можно сделать копии любого независимого множества вершин путём осуществления Y-Δ-преобразования, добавления кратных копий рёбер в полученных треугольниках, а затем осуществления обратного Δ-Y-преобразования.
Характеризация и распознавание
Если граф <math>G</math> имеет незацеплённое или плоское вложение, то любой минор графа <math>G</math> (граф, образованный стягиванием рёбер и удалением рёбер и вершин) также имеет незацепленное или плоское вложение. Удаление не может разрушить возможность незацепленного или плоского вложения, а стягивание можно осуществить, оставив одну конечную точку стягиваемого ребра на месте и переключив все рёбра, инцидентные противоположной вершине. Таким образом, по теореме Робертсона — Сеймура, имеющие незацепленное вложение графы имеют характеризацию запрещёнными графами как графы, не содержащие любого из конечного набора миноровШаблон:Sfn.
Множество запрещённых миноров для допускающих незацепленное вложение графов было выявлено СаксомШаблон:Sfn — семь графов петерсенова семейства являются минорно минимальными существенно зацепленными графами. Однако Сакс не смог доказать, что только эти графы являются минорно минимальными зацеплёнными графами, и это сделали Робертсон, Сеймур и ТомасШаблон:Sfn.
Характеризация запрещёнными минорами допускающих незацепленное вложение графов ведёт к алгоритму с полиномиальным временем работы их распознавания, но при этом этот алгоритм не строит действительное вложение. Каравабайши, Крейцер и МохарШаблон:Sfn описали алгоритм с линейным временем работы, проверяющий, вложим ли граф незацепленно, и, если вложим, строит плоское вложение графа. Их алгоритм находит большие планарные подграфы внутри заданного графа, такие, что, если существует незацепленное вложение, они представляют планарное вложение подграфа. Повторно упрощая граф, когда такой подграф находится, они сводят задачу к задаче, в которой оставшийся граф ограничен древесной шириной, и с этого момента задача может быть решена с помощью динамического программирования.
Задача эффективной проверки, является ли заданное вложение плоским или незацепленным, была поставлена Робертсоном, Сеймуром и ТомасомШаблон:Sfn. Задача остаётся нерешённой и по сложности эквивалентна задаче распутывания узла, задаче проверки, является ли кривая в пространстве незаузлённойШаблон:Sfn. Известно, что проверка незаузлённости (а следовательно, и незацепленного вложения) принадлежит классу NP, но неизвестно, принадлежит ли она классу NP-полных задачШаблон:Sfn.
Связанные семейства графов
Инвариант Колен де Вердьера — это число, определённое для любого графа на основе алгебраической теории графов. Граф с инвариантом Колен де Вердьера, не превосходящим μ, для любой фиксированной постоянной μ образует замкнутое по минорам семейство, и несколько первых таких семейств хорошо известны — графы с μ ≤ 1 представляют собой линейные леса (несвязное объединение путей), графы с μ ≤ 2 представляют собой внешнепланарные графы, а графы с μ ≤ 3 представляют собой планарные графы. Как предположили Робертсон, Сеймур и ТомасШаблон:Sfn и доказали Ловаш и СхрейверШаблон:Sfn, графами с μ ≤ 4 в точности являются графы с незацепленным вложением.
Планарные графы и вершинные графы допускают незацепленное вложение, как и графы, получаемые Y-Δ преобразованиями из нихШаблон:Sfn. YΔY сократимые графы — это графы, которые могут быть сведены к одной вершине преобразованием Y-Δ, удалением изолированных вершин и висячих вершин (вершин степени 1) и заменой дуг при вершине со степенью два одной дугой. Эти графы также замкнуты по минорам. Однако существуют незацепленные YΔY-несократимые графы, такие как вершинный граф, образованный соединением верхушки (вершины, нарушающей планарность) со всеми вершинами степени три ромбододекаэдраШаблон:Sfn. Существуют также незацепленные графы, которые не могут быть преобразованы с помощью Y-Δ-преобразований, удалением изолированных и висячих вершин и заменой дуг при вершине со степенью два одной дугой в вершинный граф. Например, корона с десятью вершинами имеет незацепленное вложение, но не может быть преобразована в вершинный граф указанным выше образомШаблон:Sfn.
Связанным с понятием незацепленного вложения является понятие незаузлённого вложения. Это такое вложение графа, что никакой простой цикл не образует нетривиальный узел. В графы, не имеющие незаузлённого вложения, входят K7 и K3,3,1,1Шаблон:SfnШаблон:Sfn. Однако существуют минимальные запрещённые миноры для незаузлённых вложений, которые не образованы (в отличие от указанных двух графов) добавлением одной вершины к существенно зацепленному графуШаблон:Sfn.
Можно определить семейства графов по присутствию или отсутствию более сложных узлов и зацеплений в их вложенииШаблон:SfnШаблон:Sfn, или по незацепленному вложению в трёхмерное многообразие, отличному от евклидова пространстваШаблон:Sfn. Флапан, Наими и ПоммершеймШаблон:Sfn определили вложение графа как трижды зацепленное, если существуют три цикла, ни один из которых не может быть отделен от двух других. Они показали, что K9 не трижды существенно зацеплены, а K10 зацеплен[1]. Более обще, можно определить n-зацепленное вложение для любого <math>n</math> как вложение, содержащее <math>n</math>-компонентное зацепление, которое не может быть разделено топологической сферой на две раздельные части. Минорно минимальные существенно <math>n</math>-зацепленные графы известны для всех <math>n</math>Шаблон:Sfn.
История
Вопрос, имеет ли <math>K_6</math> зацепленное или плоское вложение, поставил в топологическом исследовательском сообществе в начале 1970 БотеШаблон:Sfn. К незацепленному вложению привлёк внимание теоретиков графов СаксШаблон:Sfn, который предложил несколько связанных задач, включая задачу поиска характеризации запрещёнными графами графов с незацепленным или плоским вложением. Сакс показал, что семь графов петерсенова семейства (включая <math>K_6</math>) не имеют таких вложений. Как заметили Нешетрил и ТомасШаблон:Sfn, допускающие незацепленное вложение графы замкнуты по минорам графа, откуда следует по теореме Робертсона — Сеймура, что характеризация запрещёнными графами существует. Доказательство существования конечного числа препятствующих графов не ведёт к явному описанию этого множества запрещённых миноров, но из результатов Сакса следует, что семь графов петерсенова семейства принадлежат множеству. Эти задачи были окончательно решены Робертсоном, Сеймуром и ТомасомШаблон:SfnШаблон:Sfn, которые показали, что эти семь графов петерсенова семейства являются единственными минимальными запрещёнными минорами для таких графов. Таким образом, незацепленно вложимые графы и плоско вложимые графы являются одним и тем же множеством графов и оба семейства можно определить как графы, не содержащие элементы семейства петерсена в качестве миноров.
СаксШаблон:Sfn также задал вопрос о границах числа рёбер и хроматического числа вложимых без зацепления графов. Число рёбер во вложимом без зацепления графе с <math>n</math> вершинами не превосходит <math>4 n - 10</math> — максимальные вершинные графы с <math>n > 4</math> имеют в точности такое число рёберШаблон:Sfn, а МадерШаблон:Sfn доказал верность верхней границы для более общего класса свободных от K6 миноров графов. В 1985 году показано, что вопрос Сакса о хроматическом числе был бы решён, если была бы доказана гипотеза Хадвигера, что любой <math>k</math>-хроматический граф имеет в качестве минора полный граф с <math>k</math> вершинамиШаблон:Sfn. Доказательство Робертсона, Сеймура и ТомасаШаблон:Sfn случая <math>k = 6</math> гипотезы Хадвигера достаточен для решения вопроса Сакса — графы без зацеплений можно раскрасить максимум пятью цветами, поскольку любой 6-хроматический граф содержит минор <math>K_6</math> и не является незацепленным, и существуют незацепленные графы, такие как <math>K_5</math>, требующие пять цветов. Из теоремы о снарках следует, что любой кубический вложимый без зацепления граф является рёберно раскрашиваемым в 3 цвета.
Изучение вложений без зацеплений началось при исследовании алгоритмов в конце 1980-х годовШаблон:SfnШаблон:Sfn. Алгоритмически задача распознавания вложимых без зацеплений и плоско вложимых графов была решена, когда была доказана характеризация запрещёнными минорами — алгоритм Робертсона и СеймураШаблон:Sfn может быть использован для проверки за полиномиальное время, содержит ли заданный граф любой из семи запрещённых миноров[2]. Этот метод не строит незацепленное или плоское вложение, если оно существует, но алгоритм, строящий вложениеШаблон:Sfn, а позднее найден более эффективный алгоритм, работающий за линейное времяШаблон:Sfn.
На последний вопрос СаксаШаблон:Sfn о возможности аналогии теоремы Фари для незацепленных графов ответа пока нет. Вопрос ставится следующим образом: когда существование незацепленного или плоского вложения с кривыми или кусочно-линейными рёбрами влечёт существование незацепленного или плоского вложения, в котором рёбра являются отрезками?
Примечания
Литература
- Шаблон:Книга. Как процитировано в книге Робертсона, Сеймура, Томаса (Шаблон:Sfn0).
- Шаблон:Статья. Как процитировано в книге Сакса (Шаблон:Harvtxt).
- Шаблон:Статья
- Шаблон:Статья
- Шаблон:Статья
- Шаблон:Статья
- Шаблон:Статья
- Шаблон:Статья.
- Шаблон:Статья
- Шаблон:Статья
- Шаблон:Статья
- Шаблон:Статья
- Шаблон:Статья
- Шаблон:Книга
- Шаблон:Статья
- Шаблон:Статья
- Шаблон:Книга
- Шаблон:Статья
- Шаблон:Статья
- Шаблон:Книга
- Шаблон:Статья.
- Шаблон:Статья.
- Шаблон:Статья.
- Шаблон:Книга.
- Шаблон:Книга.
- Шаблон:Книга.
- Шаблон:Статья
- ↑ Для других примеров не трижды зацепленных графов см. Шаблон:Sfn0.
- ↑ Приложимость алгоритма Робертсона — Сеймура к этой задаче заметили Феллоус и Лангстон (Шаблон:Sfn0).