577
правок
Изменения
Нет описания правки
Чтобы проверить планарность графа и произвести его плоскую укладку, удобно пользоваться гамма-алгоритмом.
== Входные данные ==
На вход алгоритму подаются графы со следующими свойствами:
# [[Отношение связности, компоненты связности|Граф связный,]].# Граф содержит хотя бы один цикл,.
# Граф не имеет [[Мост, эквивалентные определения|мостов]].
Если нарушено свойство <tex>1</tex>, то граф нужно укладывать отдельно по компонентам связности. Если нарушено свойство <tex>2</tex>, то граф {{---}} дерево и нарисовать его плоскую укладку тривиально.
Более подробно рассмотрим случай, когда в графе <tex>G</tex> нарушено свойство <tex>3</tex>. Сначала все мосты нужно убрать, далее произвести отдельную укладку всех компонент следующим образом: уложим одну компоненту связности, а следующую компоненту, связанную с первой в графе <tex>G</tex> мостом, будем рисовать в той грани, в которой лежит вершина, принадлежащая мосту. Иначе может сложиться ситуация, когда концевая вершина моста будет находиться внутри плоского графа, а следующая компонента {{--- }} снаружи. Таким образом мы сможем соединить мостом нужные вершины. Далее будем так поступать с каждой новой компонентой.
== Описание алгоритма ==
Рассмотрим работу алгоритма, параллельно разбирая на примере каждый шаг.
|}
В графе <tex>G</tex> выбирается любой простой цикл и производится его укладка на плоскость. Пусть в примере это будет цикл <tex>\{1, 2, 3, 4, 5, 6\}</tex>. После его укладки получаем две грани: <tex>\Gamma_{1}</tex> и <tex>\Gamma_{2}</tex> (рис. 2).
Уже уложенную во время работы алгоритма часть будем обозначать <tex>G_{plane}</tex>. В примере сейчас <tex>G_{plane}</tex> {{---}} выбранный цикл <tex>\{1, 2, 3, 4, 5, 6\}</tex>.
Построим множество '''сегментов'''. Каждый сегмент <tex>S</tex> относительно уже построенного <tex>G_{plane}</tex> представляет собой одно из двух:
Разберем пример до конца. Повторим снова общий шаг. Теперь <tex>|\Gamma(S_{1})| = |\Gamma(S_{3})| = 1</tex>, <tex>|\Gamma(S_{2})| = |\Gamma(S_{4})| = 2</tex>. Возьмем <tex>S_{1}</tex>. В ней цепь <tex>\{2, 5\}</tex>, которую мы уложим в грань <tex>\Gamma_{2}</tex>, после чего этот сегмент исчезнет. Теперь картина будет следующая (рис. 5):
# Либо получена плоская укладка графа, либо граф оказался не планарен.
== Доказательство корректности гамма-алгоритма ==
Перед доказательством корректности приведем ряд важных вспомогательных лемм.
Заметим, что на текущем шаге нет такого сегмента <tex>S</tex> относительно <tex>G'_{k-1}</tex>, для которого бы выполнялось равенство <tex>\Gamma(S) = \emptyset</tex>, так как в противном случае существовала бы цепь этого сегмента, контактные вершины которой принадлежали бы разным граням и укладка которой была бы невозможна. Следовательно, нельзя было бы уложить <tex>S</tex>,что противоречит тому, что <tex>G</tex> {{---}} планарный граф. Значит, мы можем рассматривать только следующие два случая:
Таким образом, на каждом шаге мы получаем частичную укладку графа, что доказывает корректность гамма-алгоритма.
