logo search
КЛ

§ 7. Планарность графа

Планарность графов играет существенную роль при проектировании коммуникаций и связи между объектами на плоскости: дороги между населенными пунктами, водопроводные и газопроводные сети, линии электропередач, межсоединения на печатных платах и кристаллах интегральных схем и т.д.

Граф называется планарным (плоским ), если существует изоморфный ему граф, который может быть изображен на плоскости без пересечения ребер.

Свойства планарности не нарушаются, если некоторое ребро разбить на два ребра введением вершины второй степени или заменить два ребра, инцидентных вершине второй степени, одним ребром, удалив эту вершину.

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

Граф, гомеоморфный планарному графу, также является планарным.

Пример. Являются ли графы G и G1 (рис. 5.14) гомеоморфными?

Рис. 5.14

□ Графы G и G1 являются гомеоморфными, т.к. после удаления в графе G вершин второй степени и объединения инцидентных этим вершинам ребер u3 и u8 , u4 и u7 , u1 и u9 и после удаления в графе G1 вершин второй степени и объединения инцидентных этим вершинам ребер u3 и u8 , u1 и u7 , графы G и G1 оказываются изоморфными ( см. Глава ΙV, рис. 4.4 ). ■

Теорема (Л.С.Понтрягина). Граф планарен тогда и только тогда, когда он не содержит подграфа, гомеоморфного К5 или К3,3 .

Граф К5 – минимальный полный граф, который не является планарным (рис. 5.15). Удаление одного ребра делает этот граф планарным.

Граф К3,3 – минимальный полный двудольный граф, который не является планарным (рис. 5.15). Удаление одного ребра делает этот граф планарным.

Рис. 5.15

Толщиной графа G называется наименьшее число планарных графов, объединение которых дает граф G.

Толщина планарного графа равна 1.

Нижняя оценка толщины графа определяется неравенством

где ] [ - ближайшее целое число, степень i-ой вершины.

Замечание. Для строгого доказательства планарности графа используется теорема Понтрягина, а указанное неравенство лишь только нижняя оценка толщины графа.

Пример. Является ли граф G (рис. 5.16) планарным? Если нет, то определить, какие ребра необходимо удалить (реализовать на других плоскостях) для преобразования графа G в планарный.

Рис. 5.16

□ Согласно теореме Понтрягина проверяем граф G на содержание подграфа, гомеоморфного К5 .

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

В заданном графе G можно не удалять ни одной из вершин. Преобразования показаны на рис. 5.17

Рис. 5.17

В результате получили подграф, гомеоморфный К5 , т.е. заданный граф G не является планарным. Удаление любого ребра в полученном подграфе делает его (подграф) планарным.

Теперь проверим граф G на содержание подграфа, гомеоморфного К3,3 . Попытаемся привести граф G к виду К3,3 .

В графе К3,3 все вершины имеют степень, равную 3. В графе G степень вершин больше или равна 3, поэтому в процессе преобразования графа G вершины удалять не будем. Сведение графа G к виду графа К3,3 показано на рис. 5.18

Рис. 5.18

В результате получен подграф, гомеоморфный К3,3 . Удаление любого ребра в полученном подграфе делает его планарным.

Вывод: заданный граф G содержит подграфы, гомеоморфные К5 и К3,3. Следовательно, заданный граф G не является планарным.

Определим нижнюю оценку толщины графа G :

,

т.е. .

Так как удаление любого ребра из каждого полученного подграфа выводит их из класса подграфов, гомеоморфных К5 или К3,3 , то граф G станет планарным, если удалить ребро, входящее как в подграф, гомеоморфный К5 , так и в подграф, гомеоморфный К3,3. Таким множеством общих ребер является множество

.

Удаление любого из этих ребер делает заданный граф G планарным.

После удаления, например, ребра получаем планарный граф, плоское представление которого изображено на рис. 5.19.

Рис. 5.19

Соединение, которое соответствует удаленному ребру (показано пунктирной линией), реализуется на второй плоскости. Толщина графа G равна двум. ■