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