577
правок
Изменения
→Описание алгоритма
Итак, рассмотрим все сегменты <tex>S_{i}</tex> и для каждого определим число <tex>|\Gamma(S_{i})|</tex>. Если найдется такой номер <tex>i</tex>, что <tex>|\Gamma(S_{i})| = 0</tex>, то граф не планарен, алгоритм завершает работу. Иначе выбираем такой сегмент <tex>S_{i}</tex>, для которого число <tex>|\Gamma(S_{i})|</tex> минимально. Если таких сегментов несколько, можно выбрать любой из них. Найдем в этом сегменте цепь между двумя контактными вершинами и уложим ее в любую грань из множества <tex>|\Gamma(S_{i})|</tex>, совместив контактные вершины сегмента с соответствующими вершинами грани. Выбранная грань разобьется на две. Выбранный сегмент после того, как из него взяли цепь, либо исчезнет, либо распадется на меньшие части, в которых будут новые контактные вершины, ведущие к вершинам обновленного <tex>G_{plane}</tex>.
В примере для любого <tex>i</tex>: <tex>S_{i} \subset \{\Gamma_{1}, \Gamma_{2}\}</tex>, то есть <tex>|\Gamma(S_{i})| = 2</tex>. Следовательно, можем выбрать любой <tex>S_{i}</tex>. Пусть это будет сегмент <tex>S_{1}</tex>. В нем есть цепь <tex>\{1, 4\}</tex>. Вставим эту цепь в грань <tex>\Gamma_{1}</tex>, например, и этот сегмент исчезнет. После укладки цепи граф <tex>G</tex> и сегменты будут выглядеть так (рис. 4):
{| cellpadding="2"
| || [[Файл:Гамма-алгоритм4.jpg|thumb|left|500px|Рис. 4. Граф и сегменты после второго этапа.]]
|}
<tex>3.</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):
{| cellpadding="2"
| || [[Файл:Гамма-алгоритм5.jpg|thumb|left|500px|Рис. 5. Граф и сегменты после третьего этапа.]]
|}
