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

Гамма-алгоритм — это алгоритм плоской укладки графа и попутной проверки его на планарность.

Определения

Сегмент графа Г относительно подграфа H — компонента связности графа G\H.
Допустимая грань сегмента — грань графа H, содержащая все контактные вершины.
Контактная вершина сегмента S графа Г подграфа H — любая вершина в S и в H.
Гамма-цепь сегмента — любая цепь без повторов вершин, содержащих ровно две контактные вершины — начало и конец.

Алгоритм

Уложить на плоскость любой цикл H графа G без повторов вершин.

Построить все сегменты S₁,..,S_k графа G по H.
Если есть сегмент S_i c одной допустимой гранью — выбрать его.
Если все сегменты имеют несколько дополнительных граней — выбрать любой.
Выбрать произвольную гамма-цепь сегмента и уложить её в допустимую грань.
Перейти к шагу (2), добавив гамма-цепь к графу H.

Свойства графов для корректной работы алгоритма

Граф должен являться связным.
Граф должен иметь хотя бы один цикл.
Граф не должен иметь мостов, то есть ребер, после удаления которых, граф распадается на две компоненты связности.

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

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

Теорема

Граф Г планарен тогда и только тогда, когда гамма-алгоритм разместит его на плоскости.

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

В обратную сторону доказательство очевидно.

Докажем в прямую сторону. Если граф Г планарен, то уложенный на плоскость подграф H может быть достроен до укладки графа Г. В частности, для последнего шага это означает, что граф Г полностью уложен на плоскость.

Пусть граф Г планарен. Тогда любой цикл графа Г при укладке изображается как многоугольник. Этот многоугольник входит в укладку графа Г на плоскости.

Пусть утверждение верно вплоть до n-ой итерации алгоритма.

Варианты:

S укладывается в единственную грань графа H, граф H достраивается до укладки графа Г, и в этой укладке сегмент S лежит в единственной грани. Следовательно, укладка в этой грани любой гама-цепи C сегмента S приводит к графу H в объединение с C, достраиваемому до укладки Г.
Каждый сегмент имеет несколько допустимых граней.

Пусть S — сегмент с допустимыми гранями F₁ и F₂. Подграф H достраивается до укладки графа Г по предположению индукции. При этом, сегмент S укладывается в одну из допустимых граней. Без ограничений общности пусть эта грань F₁. Докажем, что существует продолжение H до укладки графа Г, в котором сегмент S лежит в грани F₂. Поскольку F₁ и F₂ — дополнительные грани, обе они содержат все контактные вершины сегмента S. Следовательно, все контактные вершины сегмента S лежат во множестве общих вершин F₁ и F₂. Пусть S₁,..,S_k — все сегменты, уложенные в F₁. Пусть S^'₁,..,S^'_m — все сегменты уложенные в F₂, содержащие одну из вершин. Пусть сегмент S^'_i имеет контактную вершину и другую контактную вершину не принадлежащую F₁. Тогда допустимые грани S^'_i это грань F₂, а это предположению пункта (2). Из противоречия следует, что все контактные вершины S^'_i (аналогично S_i) лежат во множестве вершин сегментов S^'₁,..,S^'_m.

Следовательно, в укладке графа Г можно сегменты S₁,..,S_k переместить в F₂, а S^'₁,..,S^'_m в F₁, это приведет к укладке графа Г в котором сегмент S лежит в грани F₂.

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

См. также

Литература

Иринёв Антон, Каширин Виктор Алгоритм плоской укладки графов [1]
Новиков И. А. Дискретная математика дл я программистов: Учебник дл я вузов. 3-е изд. — СПб.: Питер, 2009. — 384 е.: ил. — (Серия «Учебник для вузов»), ISBN 978-5-91180-759-7
Нефедов В. Н., Осипова В. А. Курс дискретной математики: Учеб. пособие.—М.; Изд-во МАИ, 1992.—264 с: ил., ISBN 5-7035-0157-X