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

Критерии планарности в практическом применении не всегда просты и не дают информации о том, как строить укладку графа на плоскости, если он планарен. Всё это вызвало появление алгоритмов, которые проверяют граф на планарность и строят его плоскую укладку. Рассмотрим один из них. Этот алгоритм представляет собой процесс последовательного присоединения к некоторому уложенному подграфу графа G новой цепи L, оба конца которой принадлежат G. После этого в качестве подграфа выбирается любой простой цикл графа G и процесс присоединения новых цепей продолжается до тех пор, пока не будет построен плоский граф, изоморфный G, или присоединение новой простой цепи на некотором этапе окажется невозможным, что свидетельствует о непланарности исходного графа G. Введём несколько определений. Пусть имеется некоторая плоская укладка подграфа графа G.

Сегментом G_i относительно называется подграф графа следующих двух видов:

1. ребро

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

Вершина u сегмента G_i называется контактной, если Граф - плоский, следовательно он разбивает плоскость на грани.

Допустимой гранью для сегмента G_i относительно называется грань Г графа , содержащая все контактные вершины сегмента G_i. Обозначим через Г(G_i) – множество допустимых граней G_i. Для непланарных графов может быть .

Рассмотрим простую цепь L сегмента G, соединяющую две различные контактные вершины и не содержащую других контактных вершин. Такие цепи называются α-цепями. Всякая α-цепь может быть уложена в любую грань, допустимую для данного сегмента.

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

1) ;

2) существуют две α- цепи , которые без пересечений нельзя уложить одновременно ни в какую грань .

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

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

2. Для некоторого сегмента G_i существует единственная допустимая грань Г. Тогда можно расположить любую α-цепь сегмента G_i в грани Г. При этом грань Г разобьётся на две грани.

3. . В этом случае можно расположить α-цепь в любой допустимой грани.

Сам алгоритм укладки планарного графа G на плоскость состоит из следующих шагов.

Шаг 1. Выбираем любой простой цикл С графа G. Этот цикл укладывается на плоскости и полагается .

Шаг 2. Находим все грани графа и все сегменты G_i относительно . Если множество сегментов пусто, происходит переход на шаг 7.

Шаг 3. Для каждого сегмента G_i определяем множество допустимых граней Г(G_i). Если найдётся сегмент G_i, для которого , то исходный граф G непланарен; конец алгоритма, иначе переход на шаг 4.

Шаг 4. Если существует сегмент G_i, для которого имеется единственная допустимая грань Г, то происходит переход на шаг 6, иначе на шаг 5.

Шаг 5. Для некоторого сегмента G_i, для которого , выбираем произвольную допустиму грань.

Шаг 6. Произвольная α – цепь сегмента G_i помещается в грань Г, заменяется на и происходит переход на шаг 1.

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

Пример 1.

Рис. 57

Шаг 1. Выберем простой цикл , который разбивает плоскость на две грани Г₁ и Г₂. Положим .

Рис. 58

Шаг 2. На приведённом выше рисунке изображён граф и сегменты G₁, G₂ исходного графа относительно . Контактные вершины обведены кружками.

Шаг 3.

Шаг 4. Нет сегмента, для которого бы существовала единственная допустимая грань.

Шаг 5. Любую α – цепь можно уложить в Г₁ или в Г₂. Выберем для укладки грань Г₁.

Шаг 6. Пусть . Поместим эту α – цепь в Г₁. Возникает новый граф и его сегменты G₁,G₂,G₃. Появляется и новая грань Г₃.

Рис. 59

Переходим к 1- ому шагу.

Шаг 1. Новых сегмента три: G₁,G₂,G₃.

Шаг 2. .

Шаг 3.

Шаг 4. , переход на шаг 6.

Шаг 6. α –цепь поместим в грань Г₁, α –цепь также помещаем в ту же грань. В результате возникает новый граф . Он имеет 5 граней и один сегмент.

Рис. 60

Шаг 1. G₁ – ребро (х₃,х₅).

Шаг 2. .

Шаг 3. .

Шаг 4. , переход на 6 –ой шаг.

Шаг 6. α – цепь поместим в грань Г₃. Новый граф является плоской укладкой исходного планарного графа.

Рис. 61

П ример 2.

Рис. 62

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

Шаг 1. Выберем простой цикл

Шаг 2. Граней у графа две: Г₁ и Г₂, сегментов 5, все они показаны на следующем рисунке.

Рис. 63

Шаг 3.

Шаг 4.

Шаг 5. Выберем для G₁ и G₅ грань Г₂ в качестве допустимой грани.

Шаг 6. α – цепи и присоединим к графу . Получим новый граф и три сегмента G₁, G₂, G₃.

Рис. 64

Шаги 1 – 2. Новых граней у графа четыре: Г₁, Г₂, Г₃, Г₄.

Шаг 3. .

Ша г4. Для G₁ и G₂ выберем грань Г₁.

Шаг 6. α – цепи и поместим в грань Г₁ и присоединим к .

Шаг 1. и сегмент G₁ показаны на следующем рисунке.

Рис. 65

Шаг 2. Граней у графа теперь 6: Г₁, Г₂, Г₃, Г₄, Г₅, Г₆.

Шаг 3. . Исходный граф G непланарен, конец алгоритма.

В заключение найдём число планарности и толщину полного графа К₅. По формуле (2) +6 = 10-15+6 = 1. Это соответствует действительности, у графа G остался один неприсоединённый сегмент G₁ (рис. 65).

Для толщины полного графа модификация формул (3) даёт точную оценку . Таким образом, этот граф можно представить в виде объединения планарных графов на двух плоскостях.

Рис. 66.