Алгоритм укладки графа на плоскости

Рассмотрим граф G=(X,V). Алгоритм укладки графа представляет собой процесс последовательного присоединения к некоторому уложенному подграфу G' (G'=(X',V')) графа G новой цепи, оба конца которой принадлежат G'. Тем самым эта цепь разбивает одну из граней G' на две. При этом в качестве начального плоского графа G' выбирается любой простой цикл графа G. Процесс продолжается до тех пор, пока не будет построен плоский граф, изоморфный графу G, или присоединение некоторой цепи окажется невозможным. В этом случае граф не является планарным.

Введем ряд определений.

Пусть построена некоторая укладка подграфа G' графа G. Сегментом S относительно G' (или просто сегментом) будем называть подграф графа G одного из следующих двух видов:

1) ребро v=(x,y) G, такое, что vÏG', x,yÎX';

2) связанную компоненту графа G\G', дополненную всеми ребрами графа G, инцидентными вершинам взятой компоненты, и концами этих ребер.

Очевидно, что в случае, когда граф G планарный, всякий сегмент, как подграф графа G, планарен, а в случае, когда G не является планарным, сегмент может быть как планарным, так и не планарным.

Вершину x сегмента S относительно G' будем называть контактной, если xÎX'.

Поскольку граф G' плоский, то он разбивает плоскость на грани. Допустимой гранью для сегмента S относительно G' называется грань Г графа G', содержащая все контактные вершины сегмента S. Через Г(S) будем обозначать множество допустимых граней для S. Может оказаться, что Г(S)=Æ.

Простую цепь L сегмента S, соединяющую две различные контактные вершины и не содержащую других контактных вершин, назовем a–цепью. Очевидно, что всякая a–цепь, принадлежащая сегменту, может быть уложена в любую грань, допустимую для этого сегмента.

Два сегмента S₁ и S₂ относительно G' назовем конфликтующими, если

1) D=Г(S₁)ÇГ(S₂)¹Æ,

2) существуют две a-цепи L₁ÎS₁_,L₂ÎS₂, которые без пересечений нельзя уложить одновременно ни в какую грань ГÎD. В противном случае будем говорить, что сегменты не конфликтуют.

Вернемся к алгоритму. На первом шаге этого алгоритма уложим произвольный простой цикл графа G.

Пусть G' – построенная на предыдущем шаге укладка некоторого подграфа графа G. Для каждого сегмента относительно G' находим множество допустимых граней. Теперь могут представиться только следующие три случая.

1. Существует сегмент, для которого нет допустимой грани. В этом случае граф не планарен.

2. Для некоторого сегмента S существует единственная допустимая грань Г. Тогда очередной шаг состоит в расположении любой a–цепи сегмента S в грани Г. При этом a–цепь разбивает грань Г на две грани.

3. для всякого сегмента S. Тогда появляется несколько вариантов продолжения построения укладки графа, поскольку любой сегмент можно размещать в любую допустимую для этого сегмента грань. Поэтому возникают опасения, что неудачный выбор сегмента и грани может помешать процессу построения укладки на следующих шагах и плоская укладка планарного графа не будет построена. Это могло бы привести к неверному заключению о том, что планарный граф непланарен. В [2] показано, что в этом случае для продолжения алгоритма можно выбирать a–цепь в любом сегменте и помещать его в любую допустимую грань.

Опишем пошагово алгоритм укладки графа на плоскости.

Шаг 1. Выберем некоторый простой цикл С графа G и уложим его на плоскости. Положим G'=С.

Шаг 2. Найдем грани графа G' и сегменты относительно G'. Если множество сегментов пусто, то перейдем к шагу 8.

Шаг 3. Для каждого сегмента S определим множество Г(S).

Шаг 4. Если существует сегмент S, для которого Г(S)=Æ, то граф G непланарен. Конец. Иначе перейти к шагу 5.

Шаг 5. Если существует сегмент S, для которого имеется единственная допустимая грань Г, то перейти к шагу 7. Иначе – к шагу 6.

Шаг 6. Для некоторого сегмента S ( ) выбираем произвольную допустимую грань Г.

Шаг 7. Поместить произвольную a–цепь LÎS в грань Г. Заменить G' на G'ÈL и перейти к шагу 2.

Шаг 8. Построена укладка G' графа G на плоскости. Конец.

Примеры. 1. Для графа G, изображенного на рис. 4.48, построить его укладку на плоскости. Уложим сначала цикл С=(1, 2, 3, 4, 1), который разбивает плоскостьна две грани Г₁ в Г₂. На рис. 4.49 изображены граф G'=С и сегменты S₁, S₂, S₃ относительно G' с контактными вершинами, обведенными кружками. Таккак Г(S_i)={Г₁, Г₂} (i=1, 2, 3), то любую a-цепь произвольного сегмента можно укладывать в любую допустимую для него грань. Поместим, например, a-цепь L=(2, 5, 4) в Г₁. Возникает новый граф G' и его сегменты (рис. 4.50). При этом Г(S₁)={Г₃}, Г(S₂)={Г₁, Г₂}, Г(S₃)={Г₁, Г₂, Г₃}. Укладываем цепь L=(1, 5) в Г₃ (рис. 4.51). Тогда Г(S₁) = {Г₁, Г₂}, Г(S₂)={Г₁, Г₂}. Далее, уложим a-цепь L=(2, 6, 4) сегмента S₁ в Г₁ (рис. 4.52). В результате имеем Г(S₁)={Г₅}, Г(S₂) ={Г₁, Г₂, Г₃}. Наконец, уложив ребро (6,3) в Г₅, а ребро (2,4) – например, а Г₁, получаем укладку графа G на плоскости (рис. 4.53).

1 2 3

6 5 4

Рис. 4.48

1 2 5 6 2

Г₂ Г₁

4 3 1 2 4 2 3 4 4

G' S₁ S₂ S₃

Рис. 4.49

1 2 5 6 2

Г₂ Г₃ Г₁

4 3 1 2 3 4 4

G' S₁ S₂ S₃

Рис. 4.50

1 2 6 2

Г₄

Г₂ Г₃ Г₁

4 3 2 3 4 4

G' S₁ S₂

Рис. 4.51

1 2 6 2

Г₄

Г₂ Г₃ Г₁

5 6

Г₅

4 3 3 4

G' S₁ S₂

Рис. 4.52

1 2

5 6

4 3

G' Рис. 4.53

2. Для графа К_3,3, изображенного на рис.4.54, построить, если это возможно, его укладку на плоскости. Цикл G' и сегменты относительно этого цикла изображены на рис. 4.55. При этом Г(S_i) = {Г_1, Г₂} (i=1,2,3). Помещает S₁ в грань Г₂. Тогда S₂ необходимо поместить в грань Г₁ (рис. 4.56). Поскольку Г(S₁)=Æ, то К_3,3 – непланарный граф.