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