Здравствуйте, Посетитель - 356777!



Граф планарен тогда и только тогда, когда он не содержит в качестве частей графы К5 и К3,3 (быть может с добавочными вершинами степени 2).

Как сделать граф плоским?
Для плоской укладки графа и попутной проверки, планарен ли он, удобно пользоваться гамма-алгоритмом.

На вход подаются графы, обладающие следующими свойствами:

1. граф связный;
2. граф имеет хотя бы один цикл;
3. граф не имеет мостиков, т. е. ребер, после удаления которых граф распадается на две компонеты связности.

Если нарушено свойство (1), то граф нужно укладывать отдельно по компонентам связности.

Если нарушено свойство (2), то граф — дерево и нарисовать его плоскую укладку тривиально.

Случай нарушения свойства (3) рассмотрим более подробно. Если в графе есть мостики, то их нужно разрезать, провести отдельно плоскую укладку каждой компоненты связности, а затем соединить их мостиками. Здесь может возникнуть трудность: в процессе укладки концевые вершины мостика могут спрятаться внутри плоского графа. Нарисуем одну компоненту связности и будем присоединять к ней другие последовательно. Каждую новую компоненту связности будем рисовать в той грани, в которой лежит концевая вершина соответствующего мостика. Так как граф связности мостиками компонент связности является деревом, мы сумеем получить плоскую укладку.

Гамма-алгоритм

1. (Инициализация). Выберем любой простой цикл C исходного графа G; изобразим его на плоскости в виде грани, которую примем за уже уложенную часть G′; сформируем сегменты Si; если множество сегментов пусто, то перейти к п. 3.
2. (Общий шаг). Пока множество сегментов непусто:
1. Для каждого сегмента S найти множество Γ(S). Если существует сегмент S, для которого |Γ(S)| = 0, то граф не планарный, конец.
2. Выбираем один из сегментов с минимальным числом, вмещающих его граней.
3. Выбираем одну из подходящих граней для выбранного сегмента.
4. В данном сегменте выбираем цепь между двумя контактными вершинами и укладываем ее в выбранной грани. Учтем изменения в структуре сегментов и перейдем к п. a).
3. (Завершение). Построена плоская укладка G′ исходного графа G, конец.

Инициализация алгоритма производится так: выбираем любой простой цикл; в нашем примере { 2, 3, 5, 6, 7, 4} и получаем две грани: Γ1 — внешнюю и Γ2 — внутреннюю



Формула Эйлера: В связном планарном графе справедливо следующее:
p+q-r=2
p - вершины
r - ребра
q - грани
P=8
q=9
r=15