577
правок
Изменения
→Гамма-алгоритм
На вход алгоритму подаются графы со следующими свойствами:
# граф Граф связный,# граф Граф содержит хотя бы один цикл,# граф Граф не имеет [[Мост, эквивалентные определения|мостов]].
Если нарушено свойство <tex>1</tex>, то граф нужно укладывать отдельно по компонентам связности. Если нарушено свойство <tex>2</tex>, то граф {{---}} дерево и нарисовать его плоскую укладку тривиально.
Более подробно рассмотрим случай, когда в графе <tex>G</tex> нарушено свойство <tex>3</tex>. Сначала все мосты нужно убрать, далее произвести отдельную укладку всех компонент следующим образом: уложим одну компоненту связности, а следующую компоненту, связанную с первой в графе <tex>G</tex> мостом, будем рисовать в той грани, в которой лежит вершина, принадлежащая мосту. Иначе может сложиться ситуация, когда концевая вершина моста будет находиться внутри плоского графа, а следующая компонента - снаружи. Таким образом мы сможем соединить мостом нужные вершины. Далее будем так поступать с каждой новой компонентой.
Рассмотрим работу алгоритма, параллельно разбирая на примере каждый шаг.
Пусть дан граф <tex>G</tex> (рис. 1).
{| cellpadding="2"
| || [[Файл:Гамма-алгоритм1.jpg|thumb|left|425px|Рис. 1. Исходный граф.]]
|}
