Планарные графы

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

планарный граф гамма алгоритм

Плоские графы

На рис. 1 показаны два геометрических графа и, представляющих, как нетрудно проверить, один и тот же обыкновенный граф. Простое устройство этого графа, очевидное на изображении слева, не так легко обнаружить, рассматривая изображение справа. Главная причина этого в том, что в ребра не имеют «лишних» пересечений.

Рис.1

Геометрический граф, в котором никакие два ребра не имеют общих точек, кроме инцидентной им обоим вершины, называют плоским графом, а по отношению к представляемому им обыкновенному графу — его плоской укладкой. Не каждый граф допускает плоскую укладку. Граф, для которого существует плоская укладка, называется планарным графом.

Планарные графы

Теорема (формула Эйлера). Количество граней в любой плоской укладке планарного графа, имеющего вершин, ребер и компонент связности, равно. Доказательство. Докажем сначала утверждение теоремы при. Рассмотрим связный плоский граф. Если в нем нет циклов, то имеется единственная грань, а, и формула верна. Если же есть хотя бы один цикл, то возьмем какое-нибудь ребро, принадлежащее простому циклу. Это ребро принадлежит границе двух граней, одна из которых целиком лежит внутри цикла, другая — снаружи. Если удалить ребро из графа, эти две грани сольются в одну. Граф, полученный из графа удалением ребра, очевидно, будет плоским и связным, в нем на одно ребро и на одну грань меньше, чем в, а число вершин осталось прежним. Если в еще есть циклы, то, удалив еще одно цикловое ребро, получим граф. Будем продолжать удаление цикловых ребер до тех пор, пока не получится связный плоский граф без циклов, т. е. дерево. У него ребро и единственная грань. Значит, всего было удалено ребер, а так как при удалении каждого ребра число граней уменьшалось на единицу, то в исходном графе было грани. Таким образом, формула верна для любого связного плоского графа. Если граф несвязен, то в компоненте связности, имеющей вершин и ребер, как доказано выше, будет внутренняя грань. Суммируя по всем компонентам и прибавляя 1 для учета внешней грани, убеждаемся в справедливости формулы в общем случае. Следствие 1 Если в планарном графе вершин,, и ребер, то Доказательство Если в графе нет циклов, то и неравенство выполняется при. Рассмотрим плоский граф с гранями, в котором имеются циклы. Занумеруем грани числами от до и обозначим через количество ребер, принадлежащих грани с номером. Так как граница каждой грани содержит цикл, то для каждого, следовательно,. С другой стороны, каждое ребро принадлежит границе не более чем двух граней, поэтому. Из этих двух неравенств следует, что. Применяя формулу Эйлера, получаем. Следствие 1 дает необходимое условие планарности, которое в некоторых случаях позволяет установить, что граф не является планарным. Рассмотрим, например, полный граф. У него, , и мы видим, что неравенство из следствия 1 не выполняется. Значит, этот граф непланарен. В то же время существуют графы, не являющиеся планарными, для которых неравенство следствия 1 выполняется. Пример — полный двудольный граф. У него 6 вершин и 9 ребер. Неравенство выполняется, но мы сейчас установим, что он непланарен. Заметим, что в этом графе нет циклов длины 3 (так как он двудольный, в нем вообще нет циклов нечетной длины). Поэтому граница каждой грани содержит не менее четырех ребер. Повторяя рассуждения из доказательства следствия 1, но используя неравенство вместо, получаем следующий результат:

Следствие 2 Если в планарном графе вершин,, ребер и нет циклов длины, то .

Для графа неравенство следствия 2 не выполняется, и это доказывает, что он непланарен.

Два критерия планарности

Известно несколько критериев планарности, сформулируем без доказательства два из них. Два графа называют гомеоморфными, если из них с помощью подразбиения ребер можно получить изоморфные графы. На рис. 3 изображены гомеоморфные графы.

Рис. 3 Теорема (критерий Понтрягина — Куратовского) Граф планарен тогда и только тогда, когда у него нет подграфов, гомеоморфных или. Теорема (критерий Вагнера). Граф планарен тогда и только тогда, когда у него нет подграфов, стягиваемых к или. Граф называется стягиваемым к графу, если можно получить из последовательностью операций стягивания ребер.

Отметим, что, несмотря на внешнее сходство двух теорем, фигурирующие в них понятия гомеоморфизма и стягиваемости существенно различаются. На рис. 3 изображен граф, который называют графом Петерсена. В нем нет подграфа, гомеоморфного, так как в графе каждая вершина имеет степень, а в графе Петерсена степень каждой вершины равна. При удалении вершин и ребер и подразбиении ребер степени вершин не увеличиваются. В то же время легко видеть, что граф Петерсена можно превратить в стягиванием пяти ребер.

Рис.3

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

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

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

1. граф связный;

2. граф имеет хотя бы один цикл;

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

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

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

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

Сначала изложим алгоритм на конкретном примере. Пусть дан граф G (см. рис. 3).

Рис.

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

Рис.

Обозначим выбранный цикл как G?. На каждом шаге будем строить множество сегментов. Каждый сегмент S относительно уже построенного графа G? представляет собой одно из двух:

· ребро, оба конца которого принадлежат G?, но само оно не принадлежит G?;

· связную компоненту графа G — G?, дополненную всеми ребрами графа G, один из концов которых принадлежит связной компоненте, а второй из графа G?.

Те вершины, которые одновременно принадлежат G? и какому-то сегменту, назовем контактными. Для нашего примера сегменты и вершины изображены на рис. 5. Контактные вершины обведены в квадрат.

Рис.

Если бы в каком-нибудь сегменте не было ни одной контактной вершины, то граф до разрезания был бы несвязный; если бы была только одна, то граф имел бы мостик. Эти возможности заранее исключены, так что каждый сегмент имеет не менее двух контактных вершин. Поэтому в каждом сегменте имеется цепь между любой парой таких вершин. Если все контактные вершины сегмента S имеют номера вершин какой-то грани ?, то мы будем говорить, что грань? вмещает этот сегмент и обозначать S??. Может быть имеется не одна такая грань, вмещающая сегмент S, множество таких граней обозначим ?(S), а их число |?(S)|.

Общий шаг алгоритма следующий: обозреваются все сегменты S_i и определяются числа |?(S_i)|. Если хоть одно из них равно 0, то граф не планарен, конец. Иначе, выбираем сегмент, для которого число |?(S)| минимально, или один из множества, если таких сегментов несколько. В этом сегменте найдем цепь между двумя контактными вершинами и уложим ее в любую из граней множества ?(S), совместив контактные вершины сегмента с соответствующими вершинами грани. При этом данная грань разобьется на две. Уже уложенная часть графа G? по количеству ребер и вершин увеличится, а сегмент, из которого вынута цепь, исчезнет или развалится на меньшие с новыми контактными вершинами, ведущими к вершинам G?.

В результате повторения общего шага либо будет получена плоская укладка, когда множество сегментов станет пустым, либо будет получено, что граф G не является планарным. Вернемся к нашему примеру. Пока для любого i: S_i?{?₁, ?₂}, |?(S_i)| = 2. Поэтому возьмем первый по номеру сегмент S_i и в нем первую попавшеюся цепь {4, 8}; вставим эту цепь в грань ?₂. Получим увеличенную часть G? и уменьшенную систему сегментов (см. рис. 6 a, b).

Рис.

Определим какие грани вмещают новые сегменты. Теперь сегменты S₁ и S₂ вмещаются только в одну грань ?₁, в то время, как сегмент S₃ вмещается в две грани ?₁ и ?₃. Поэтому берем S₁. Возьмем в нем цепь между контактными вершинами, например, {2, 7}, и уложим ее в ?₁. Получим увеличенную часть G? и уменьшенную систему сегментов (см. рис. 7 a, b).

Рис.

Продолжая таким образом, в итоге получим плоскую укладку G (см. рис. 8).

Рис.

Еще раз опишем гамма-алгоритм компактно и займемся его обоснованием.

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

1. (Инициализация). Выберем любой простой цикл C исходного графа G; изобразим его на плоскости в виде грани, которую примем за уже уложенную часть G?; сформируем сегменты S_i; если множество сегментов пусто, то перейти к п. 3.

2. (Общий шаг). Пока множество сегментов непусто:

a. Для каждого сегмента S найти множество ?(S). Если существует сегмент S, для которого |?(S)| = 0, то граф не планарный, конец.

b. Выбираем один из сегментов с минимальным числом, вмещающих его граней.

c. Выбираем одну из подходящих граней для выбранного сегмента.

d. В данном сегменте выбираем цепь между двумя контактными вершинами и укладываем ее в выбранной грани. Учтем изменения в структуре сегментов и перейдем к п. a).

3. (Завершение). Построена плоская укладка G? исходного графа G, конец.

1.Планарные графы // Интернет ресурс: http://www.intuit.ru/department/algorithms/gaa/¾.html

2.Теория графов // Интернет ресурс: http://www.intuit.ru/department/ds/discretemath/6/

3.АсановМ.О., Баранский В. А., Дискртеная математика: — Ижевск: НИЦ «РХД», 2001,288 стр.