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

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

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

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

1. граф связный;
2. граф имеет хотя бы один цикл;
3. граф не имеет мостиков, т. е. ребер, после удаления которых граф распадается на две компонеты связности.

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

Если нарушено свойство (2), то граф — дерево и нарисовать его плоскую укладку тривиально.

Случай нарушения свойства (3) рассмотрим более подробно. Если в графе есть мостики, то их нужно  разрезать, провести отдельно плоскую  укладку каждой компоненты связности, а затем соединить их мостиками. Здесь может возникнуть трудность: в процессе укладки концевые вершины  мостика могут спрятаться внутри плоского графа. Нарисуем одну компоненту связности и будем присоединять к ней другие последовательно. Каждую новую компоненту связности будем  рисовать в той грани, в которой  лежит концевая вершина соответствующего мостика. Так как граф связности  мостиками компонент связности  является деревом, мы сумеем получить плоскую укладку.

Сначала изложим алгоритм на конкретном примере. Пусть дан  граф G (см. рис. 3).

Инициализация алгоритма  производится так: выбираем любой простой  цикл; в нашем примере {1, 2, 3, 4, 5, 6, 7, 8} и получаем две грани: Γ₁ — внешнюю и Γ₂ — внутреннюю (см. рис. 4).

Обозначим выбранный цикл как G′. На каждом шаге будем строить множество сегментов. Каждый сегмент S относительно уже построенного графа G′ представляет собой одно из двух:

• ребро, оба конца которого принадлежат G′, но само оно не принадлежит G′;
• связную компоненту графа G – G′, дополненную всеми ребрами графа G, один из концов которых принадлежит связной компоненте, а второй из графа G′.

Те вершины, которые одновременно принадлежат G′ и какому-то сегменту, назовем контактными. Для нашего примера сегменты и вершины изображены на рис. 5. Контактные вершины обведены в квадрат.

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

Если все контактные вершины  сегмента S имеют номера вершин какой-то грани Γ, то мы будем говорить, что грань Γ вмещает этот сегмент и обозначать S⊂Γ. Может быть имеется не одна такая грань, вмещающая сегмент S, множество таких граней обозначим Γ(S), а их число |Γ(S)|.

Общий шаг алгоритма следующий: обозреваются все сегменты S_i и определяются числа |Γ(S_i)|. Если хоть одно из них равно 0, то граф не планарен, конец. Иначе, выбираем сегмент, для которого число |Γ(S)| минимально, или один из множества, если таких сегментов несколько. В этом сегменте найдем цепь между двумя контактными вершинами и уложим ее в любую из граней множества Γ(S), совместив контактные вершины сегмента с соответствующими вершинами грани. При этом данная грань разобьется на две. Уже уложенная часть графа G′ по количеству ребер и вершин увеличится, а сегмент, из которого вынута цепь, исчезнет или развалится на меньшие с новыми контактными вершинами, ведущими к вершинам G′.

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

Вернемся к нашему примеру. Пока для любого i: S_i⊂{Γ₁, Γ₂}, |Γ(S_i)| = 2. Поэтому возьмем первый по номеру сегмент S_i и в нем первую попавшеюся цепь {4, 8}; вставим эту цепь в грань Γ₂. Получим увеличенную часть G′ и уменьшенную систему сегментов (см. рис. 6 a, b).

Определим какие грани вмещают новые сегменты. Теперь сегменты S₁ и S₂ вмещаются только в одну грань Γ₁, в то время, как сегмент S₃ вмещается в две грани Γ₁ и Γ₃. Поэтому берем S₁. Возьмем в нем цепь между контактными вершинами, например, {2, 7}, и уложим ее в Γ₁. Получим увеличенную часть G′ и уменьшенную систему сегментов (см. рис. 7 a, b).

Продолжая таким образом, в итоге получим плоскую укладку G (см. рис. 8).

Еще раз опишем гамма-алгоритм компактно и займемся его обоснованием.

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

1. (Инициализация). Выберем любой простой цикл C исходного графа G; изобразим его на плоскости в виде грани, которую примем за уже уложенную часть G′; сформируем сегменты S_i; если множество сегментов пусто, то перейти к п. 3.
2. (Общий шаг). Пока множество сегментов непусто:
1. Для каждого сегмента S найти множество Γ(S). Если существует сегмент S, для которого |Γ(S)| = 0, то граф не планарный, конец.
2. Выбираем один из сегментов с минимальным числом, вмещающих его граней.
3. Выбираем одну из подходящих граней для выбранного сегмента.
4. В данном сегменте выбираем цепь между двумя контактными вершинами и укладываем ее в выбранной грани. Учтем изменения в структуре сегментов и перейдем к п. a).
3. (Завершение). Построена плоская укладка G′ исходного графа G, конец.