Гамма-алгоритм

Задача:

Определить, является ли граф планарным, и, если да, произвести его плоскую укладку.

Существует теорема Понтрягина-Куратовского, которая говорит, что граф планарен тогда и только тогда, когда он не содержит подграфов, гомеоморфных [math] K_{5} [/math] или [math] K_{3, 3} [/math]. Но этот критерий очень трудно проверить на практике, поэтому данная теорема представляет лишь теоретический интерес.

Чтобы проверить планарность графа и произвести его плоскую укладку, удобно пользоваться гамма-алгоритмом.

Входные данные

На вход алгоритму подаются графы со следующими свойствами:

1. Граф связный.
2. Граф содержит хотя бы один цикл.
3. Граф не имеет мостов.

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

Более подробно рассмотрим случай, когда в графе [math]G[/math] нарушено свойство 3. Сначала все мосты нужно убрать, далее произвести отдельную укладку всех компонент следующим образом: уложим одну компоненту связности, а следующую компоненту, связанную с первой в графе [math]G[/math] мостом, будем рисовать в той грани, в которой лежит вершина, принадлежащая мосту. Иначе может сложиться ситуация, когда концевая вершина моста будет находиться внутри плоского графа, а следующая компонента — снаружи. Таким образом мы сможем соединить мостом нужные вершины. Далее будем так поступать с каждой новой компонентой.

Описание алгоритма

Рассмотрим работу алгоритма, параллельно разбирая на примере каждый шаг. Пусть дан граф [math]G[/math] (рис. 1).

Рис. 1. Исходный граф.

1.Первый этап - инициализация алгоритма.

В графе [math]G[/math] выбирается любой простой цикл и производится его укладка на плоскость. Пусть в примере это будет цикл [math]\{1, 2, 3, 4, 5, 6\}[/math]. После его укладки получаем две грани: [math]\Gamma_{1}[/math] и [math]\Gamma_{2}[/math] (рис. 2).

Рис. 2. Укладка цикла на плоскость.

Уже уложенную во время работы алгоритма часть будем обозначать [math]G_{plane}[/math]. В примере сейчас [math]G_{plane}[/math] — выбранный цикл [math]\{1, 2, 3, 4, 5, 6\}[/math].

2. Второй этап - общий шаг.

Построим множество сегментов. Каждый сегмент [math]S[/math] относительно уже построенного [math]G_{plane}[/math] представляет собой одно из двух:

1. ребро, оба конца которого принадлежат [math]G_{plane}[/math], но само оно не принадлежит [math]G_{plane}[/math],
2. связную компоненту графа [math]G \backslash G_{plane}[/math], дополненную всеми ребрами графа [math]G[/math] такими, у которых один из концов принадлежит связной компоненте, а второй принадлежит графу [math]G_{plane}[/math].

Вершины, одновременно принадлежащие [math]G_{plane}[/math] и какому-либо сегменту, назовем контактными. На рис. 3 изображены сегменты для нашего примера. Контактные вершины обведены в квадрат.

Рис. 3. Выделение сегментов.

Пусть в каком-то сегменте нет ни одной контактной вершины. В таком случае граф до выделения [math]G_{plane}[/math] был несвязным, что противоречит условию. Пусть контактная вершина в сегменте только одна. Это значит, что в графе был мост, чего быть не может так же по условию. Таким образом, в каждом сегменте имеется не менее двух контактных вершин. Соответственно, в каждом сегменте есть цепь между любой парой контактных вершин.

Пусть грань [math]\Gamma[/math] вмещает сегмент [math]S[/math], если номера всех контактных вершин [math]S[/math] принадлежат этой грани, [math]S \subset \Gamma[/math]. Очевидно, таких граней может быть несколько. Множество таких граней обозначим [math]\Gamma(S)[/math], а их число — [math]|\Gamma(S)|[/math].

Итак, рассмотрим все сегменты [math]S_{i}[/math] и для каждого определим число [math]|\Gamma(S_{i})|[/math]. Если найдется такой номер [math]i[/math], что [math]|\Gamma(S_{i})| = 0[/math], то граф не планарен, алгоритм завершает работу. Иначе выбираем такой сегмент [math]S_{i}[/math], для которого число [math]|\Gamma(S_{i})|[/math] минимально. Если таких сегментов несколько, можно выбрать любой из них. Найдем в этом сегменте цепь между двумя контактными вершинами и уложим ее в любую грань из множества [math]|\Gamma(S_{i})|[/math], совместив контактные вершины сегмента с соответствующими вершинами грани. Выбранная грань разобьется на две. Выбранный сегмент после того, как из него взяли цепь, либо исчезнет, либо распадется на меньшие части, в которых будут новые контактные вершины, ведущие к вершинам обновленного [math]G_{plane}[/math].

В примере для любого [math]i[/math]: [math]S_{i} \subset \{\Gamma_{1}, \Gamma_{2}\}[/math], то есть [math]|\Gamma(S_{i})| = 2[/math]. Следовательно, можем выбрать любой [math]S_{i}[/math]. Пусть это будет сегмент [math]S_{1}[/math]. В нем есть цепь [math]\{1, 4\}[/math]. Вставим эту цепь в грань [math]\Gamma_{1}[/math], например, и этот сегмент исчезнет. После укладки цепи граф [math]G[/math] и сегменты будут выглядеть так (рис. 4):

Рис. 4. Граф и сегменты после второго этапа.

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

Разберем пример до конца. Повторим снова общий шаг. Теперь [math]|\Gamma(S_{1})| = |\Gamma(S_{3})| = 1[/math], [math]|\Gamma(S_{2})| = |\Gamma(S_{4})| = 2[/math]. Возьмем [math]S_{1}[/math]. В ней цепь [math]\{2, 5\}[/math], которую мы уложим в грань [math]\Gamma_{2}[/math], после чего этот сегмент исчезнет. Теперь картина будет следующая (рис. 5):

Рис. 5. Граф и сегменты после третьего этапа.

На следующем шаге [math]|\Gamma(S_{1})| = |\Gamma(S_{3})| = 2[/math], [math]|\Gamma(S_{2})| = 1[/math]. Выбираем сегмент [math]S_{2}[/math], содержащий цепь [math]\{3, 5\}[/math]. Уложим ее в грань [math]\Gamma_{2}[/math], после чего этот сегмент снова исчезнет (рис. 6).

Рис. 6. Граф и сегменты после четвертого этапа.

Теперь [math]|\Gamma(S_{1})| = 1[/math], а [math]|\Gamma(S_{3})| = 2[/math]. Уложим сначала цепь [math]\{2, 4\}[/math] из первого сегмента, он пропадет, потом уложим цепь [math]\{6, 7, 5\}[/math] из третьего. В результате граф будет полностью уложен на плоскость, множество сегментов останется пустым (рис. 7).

Рис. 7. Плоская укладка графа.

Таким образом, мы получили плоскую укладку исходного графа [math]G[/math].

Опишем алгоритм коротко и формально:

1. Инициализация. Выбирается простой цикл в исходном графе и изображается на плоскости.
2. Общий шаг. Этот шаг повторяется до тех пор, пока граф не будет уложен или пока не будет получено, что граф не планарен.
   • строится множество сегментов
   • для каждого сегмента вычисляется величина [math]|\Gamma(S)|[/math]. Если существует [math]i[/math]: [math]|\Gamma(S_{i})| = 0[/math], то граф не планарен, алгоритм завершает работу
   • выбирается сегмент с минимальным числом [math]|\Gamma(S_{i})|[/math]
   • в этом сегменте выбирается цепь между двумя контактными вершинами
   • эта цепь укладывается в любую грань, вмещающую данный сегмент
3. Либо получена плоская укладка графа, либо граф оказался не планарен.

Доказательство корректности гамма-алгоритма

Перед доказательством корректности приведем ряд важных вспомогательных лемм.

Пусть два сегмента [math]S_{1}[/math] и [math]S_{2}[/math] называются конфликтующими относительно уже уложенной части, если:

1. грань вмещает каждый из сегментов [math]S_{1}[/math] и [math]S_{2}[/math]
2. в этих сегментах есть две цепи между контактными вершинами [math]L_{1}[/math] и [math]L_{2}[/math] соответственно такие, что их невозможно уложить в одну грань без пересечения

Например, на рис. 1 конфликтующими являются сегменты [math]S_{1}[/math] и [math]S_{2}[/math].

Рис. 1. Конфликтующие сегменты.

Лемма (1):

Конфликтующие сегменты [math]S_{1}[/math] и [math]S_{2}[/math] обладают следующим свойством: если [math]|\Gamma(S_{1})| \geq 2[/math] и [math]|\Gamma(S_{2})| \geq 2[/math], то [math]\Gamma(S_{1}) = \Gamma(S_{2}) = 2[/math].

Доказательство:

[math]\triangleright[/math]

Сначала докажем, что [math]\Gamma(S_{1}) = \Gamma(S_{2})[/math]. Предположим противное. Тогда по условию леммы найдутся три различные грани [math]\Gamma_{1}, \Gamma_{2}[/math] и [math]\Gamma_{3}[/math] такие, что [math]\Gamma_{1} \in \Gamma(S_{1}), \Gamma_{2} \in \Gamma(S_{2}), \Gamma_{3} \in Q = \Gamma(S_{1}) \cap \Gamma(S_{2}) \neq \emptyset[/math]. Тогда любые цепи [math]L_{1} \subset S_{1}[/math] и [math]L_{2} \subset S_{2}[/math] укладываются в [math]\Gamma_{1}[/math] и [math]\Gamma_{2}[/math] соответственно. Но это значит, что любая пара цепей [math]L_{1}[/math] и [math]L_{2}[/math] одновременно укладывается вне грани [math]\Gamma_{3}[/math]. Следовательно, они одновременно укладываются и внутри грани [math]\Gamma_{3}[/math], причем без пересечений. Но это противоречит тому, что [math]S_{1}[/math] и [math]S_{2}[/math] — конфликтующие сегменты. Таким образом, [math]\Gamma(S_{1}) = \Gamma(S_{2})[/math]. Теперь покажем, что [math]|Q| = 2[/math]. Доказательство снова поведем методом от противного. Пусть [math]|Q| \geq 3[/math]. Тогда снова существует три различные грани [math]\Gamma_{1}, \Gamma_{2}[/math] и [math]\Gamma_{3} \in Q[/math]. Аналогичными рассуждениями снова приходим к противоречию с тем, что [math]S_{1}[/math] и [math]S_{2}[/math] — конфликтующие сегменты.

[math]\triangleleft[/math]

Замечание. Пусть имеется множество сегментов таких, что они удовлетворяют следующей схеме: есть первый сегмент [math]S_{1}[/math], второй [math]S_{2}[/math], который конфликтует с [math]S_{1}[/math], третий [math]S_{3}[/math], который конфликтует с [math]S_{2}[/math], но не с [math]S_{1}[/math], и так далее, причем каждый из них укладывается в две грани. Тогда из леммы 1 следует, что эти грани являются общими для всех сегментов множества и можно укладывать их следующим образом: цепь [math]L_{1} \subset S_{1}[/math] укладывается в первую грань [math]\Gamma_{1}[/math], цепь [math]L_{2} \subset S_{2}[/math] — во вторую [math]\Gamma_{2}[/math], [math]L_{3} \subset S_{3}[/math] — снова в [math]\Gamma_{1}[/math] и так для всех элементов множества. Если цепочка сегментов замыкается в цикл четной длины, то проблем никаких нет. Если длина цикла нечетная, то два последних конфликтующих сегмента нужно будет уложить в одну грань без пересечений, что по определению невозможно. Следовательно, получить плоскую укладку нельзя.

Определение:

Частичной укладкой [math]G'[/math] планарного графа [math]G[/math] называется граф, который можно получить из какой-либо укладки графа [math]G[/math] на плоскости путем удаления некоторых ребер и вершин.

Таким образом во всякую частичную укладку планарного графа [math]G[/math] можно уложить оставшуюся часть, а именно недостающие вершины и ребра графа [math]G[/math].

Построим некоторый служебный граф [math]A(G')[/math] по следующей схеме: каждому сегменту в [math]G'[/math] сопоставим некоторую вершину в [math]A(G')[/math], причем две вершины будут смежны тогда и только тогда, когда соответствующие им сегменты являются конфликтующими.

Например, для графа на рис. 1 служебный граф будет иметь вид (рис. 2):

Рис. 2. Служебный граф. Вершины обозначены как соответствующие сегменты.

Лемма (2):

Если результатом некоторого шага работы гамма-алгоритма является частичная укладка [math]G'[/math] планарного графа [math]G[/math] такая, что [math]|\Gamma(S)| \geq 2[/math] для любого сегмента [math]S[/math] относительно [math]G'[/math], то [math]A(G')[/math] — двудольный граф.

Доказательство:

[math]\triangleright[/math]

Докажем от противного. Пусть [math]A(G')[/math] — не двудольный. Тогда по теореме Кенинга в нем есть цикл нечетной длины. Этому циклу соответствует некоторая последовательность сегментов [math]S_{1}, S_{2}, \cdots S_{2m+1}, S_{1}[/math] относительно [math]G'[/math], в которой каждые соседние сегменты конфликтующие по определению. По лемме 1 [math]\Gamma(S_{i}) = \{\Gamma_{1}, \Gamma_{2}\}, i \in \{1 \cdots 2m+1\}[/math]. Так как [math]G'[/math] — частичная укладка графа, то все сегменты [math]S_{1}, S_{2}, \cdots S_{2m+1}[/math] могут быть уложены. А так как соседние сегменты этой последовательности конфликтующие, то они должны быть уложены в разные грани, что невозможно, так как число сегментов в последовательности нечетное. Получили противоречие. Следовательно, [math]A(G')[/math] — двудольный.

[math]\triangleleft[/math]

Теорема (О корректности гамма-алгоритма):

Гамма-алгоритм корректен, то есть если [math]G[/math] — планарный граф, то результатом каждого шага гамма-алгоритма является частичная укладка [math]G'[/math].

Доказательство:

[math]\triangleright[/math]

Докажем индукцией по числу шагов. База индукции: полученный на этапе инициализации граф [math]G'_{0}[/math] является простым циклом, он будет присутствовать в любой укладке графа [math]G[/math]. Таким образом, [math]G'_{0}[/math] является частичной укладкой. Шаг индукции: пусть граф [math]G'_{k-1}[/math], полученный на [math]k-1[/math]-м шаге работы алгоритма, является частичной укладкой. Докажем, что граф [math]G'_{k} = G'_{k-1} \cup L_{k}[/math], полученный на [math]k[/math]-м шаге присоединением цепи [math]L_{k}[/math], также является частичной укладкой. Заметим, что на текущем шаге нет такого сегмента [math]S[/math] относительно [math]G'_{k-1}[/math], для которого бы выполнялось равенство [math]\Gamma(S) = \emptyset[/math], так как в противном случае существовала бы цепь этого сегмента, контактные вершины которой принадлежали бы разным граням и укладка которой была бы невозможна. Следовательно, нельзя было бы уложить [math]S[/math],что противоречит тому, что [math]G[/math] — планарный граф. Значит, мы можем рассматривать только следующие два случая: 1. Существует сегмент [math]S[/math] для которого есть единственная вмещающая грань [math]\Gamma[/math], то есть [math]|\Gamma(S)| = 1[/math]. Так как только грани [math]\Gamma[/math] принадлежат все контактные вершины [math]S[/math], то укладка этого сегмента в эту грань неизбежна. Это значит, что помещая любую цепь [math]L \subset S[/math], снова получим частичную укладку графа. 2. Для любого сегмента [math]S[/math] [math]|\Gamma(S)| \geq 2[/math]. Построим граф [math]A(G'_{k-1})[/math], который по лемме 2 является двудольным. Рассмотрим его связную компоненту [math]K[/math], которая содержит не менее двух вершин. Граф [math]K[/math] также является двудольным. По лемме 1 для любого сегмента [math]S \in K[/math] справедливо [math]\Gamma(S) = \{\Gamma_{1}, \Gamma_{2}\}[/math]. Так как граф [math]K[/math] двудольный, то мы можем по очереди помещать сегменты [math]K[/math] в разные грани, причем конфликтующих сегментов не возникнет в силу четности всех циклов в графе. Результатом будет частичная укладка графа. Таким образом, на каждом шаге мы получаем частичную укладку графа, что доказывает корректность гамма-алгоритма.

[math]\triangleleft[/math]

Следствие: Если граф [math]G[/math] планарный, то гамма-алгоритм строит его плоскую укладку.

Следствие: Если на каком-то шаге встретился сегмент [math]S[/math], для которого нет вмещающей грани, то граф непланарный.

См. также

• Теорема Понтрягина-Куратовского

Источники информации

• Дискретная математика: алгоритмы