Вопросы для самоконтроля

1. Что такое число внутренней устойчивости графа?

2. Что такое независимое подмножество вершин графа?

3. Каким образом выделяется независимое подмножество вершин графа?

4. Какое подмножество вершин графа называется предельным?

5. Приведите механизм определения внутренне устойчивых подмножеств.

6. Опишите идею алгоритма выделения независимых подмножеств в графе.

7. Что такое число внешней устойчивости?

8. Приведите механизм определения внешне устойчивых подмножеств.

9. Что такое минимальное внешне устойчивое подмножество?

10. Опишите основную идею алгоритма выделения минимальных внешне устойчивых подмножеств.

Задания для самостоятельной работы

1. Для произвольного G = (X, U) графа определить число внутренней устойчивости.

2. Определить число внутренней устойчивости произвольного графа G = (X, U) и построить семейство независимых подмножеств.

3. Для произвольного графа G = (X, U) построить раскраску на основе алгоритма выделения независимых подмножеств.

4. Для произвольного графа G = (X, U) определить число внешней устойчивости и применить алгоритм выделения минимальных внешне устойчивых подмножеств.

5. Постройте структурную схему алгоритма нахождения семейства независимых подмножеств.

6. Запишите псевдокод алгоритма построения семейства независимых подмножеств.

7. Постройте структурную схему алгоритма определения семейства доминирующих подмножеств в графе.

8. Постройте псевдокод алгоритма определения семейства доминирующих подмножеств в графе.

9. Запишите псевдокод алгоритма раскраски графа путем нахождения минимального покрытия независимыми подмножествами.

10. Постройте структурную схему алгоритма раскраски графа путем нахождения минимального покрытия независимыми подмножествами.

Числа внутренней и внешней устойчивости относятся к инвариантам графа. Они позволяют определить специальные группы вершин в графах.

17.3. Планарность графов

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

17.3.1. Плоские и планарные графы

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

Области, определяемые плоским графом (ПЛГ), называются его внутренними гранями или просто гранями. Если границей грани ПЛГ является простой цикл, то иногда под гранью понимают этот цикл. ПЛГ (рис. 17.9) имеет две внутренние грани f1, f2 и одну внешнюю – f3. Неограниченная область называется внешней гранью.

Рис. 17.9. Плоский граф с тремя гранями

Плоской картой называется связный ПЛГ вместе со всеми его гранями. Уравнение (теорема) Эйлера для плоской карты с n–вершинами, m–ребрами и f–гранями запишется как

Теорема 17.4

n – m + f = 2. (17.13)

Следствие 17.1. Если G – плоская (n, m) – карта, в которой каждая грань является С-циклом (т.е. циклом длиной С, состоящим из С ребер), то

(17.14)

и

m = Сf / 2. (17.15)

Максимальным планарным графом (МПГ) называется граф, который при добавлении любого ребра перестает быть планарным.

Следствие 17.2. Если G – МПГ, то каждая его грань является треугольником и

m = 3n – 6. (17.16)

Если G – плоский граф, у которого любая грань есть 4–цикл, то

m = 2n – 4. (17.17)

Так как наибольшим числом ребер в ПЛГ обладает граф, у которого каждая грань есть треугольник, то получаем необходимое условие планарности графа в терминах числа ребер.

Следствие 17.3. Графы K₅ и K_3,3 не являются планарными.

На рис. 17.10,а показан граф K₅, а на рис. 17.10,б – K_3,3.

а

б

Рис. 17.10. Полный граф K₅ (а), полный двудольный граф K_3,3 (б)

Доказательство. K₅ есть граф c 5 вершинами 10 ребрами, и он не может быть планарным, так как m= 10 > 3n - 6 = 9. Для K_3,3 имеем m = 9 > 2n – 4 = 8, что и доказывает следствие 17.3.

Легко видеть, что каждый подграф ПЛГ – планарен, а любой граф, содержащий в качестве подграфа непланарный граф (НПГ), сам не может быть планарным. Отсюда вытекает, что K₅ и K_3,3 – по существу единственные непланарные графы в том смысле, что любой НПГ содержит один из них.

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

Л.С. Понтрягин в 1927г. доказал, но не опубликовал критерий планарности.

К. Куратовский в 1930 г. независимо от Л.С. Понтрягина получил тот же результат.

Теорема 17.5. (Понтрягин – Куратовский). Граф планарен тогда и только тогда, когда он не содержит подграфа гомеоморфного графам K₅ или K_3,3.

Граф G называется стягиваемым к графу Н, если Н можно получить из G с помощью некоторой последовательности элементарных стягиваний. Например, на рис. 3.11 показано как граф Петерсона стягивается в K₅. Здесь произошло стягивание в новую вершину w_i любого из пяти ребер (u_i, v_i), соединяющего пятиугольник с пентаграммой (звездой). Т.е. K₅ получается из графа Петерсона стягиванием 5 ребер внутреннего цикла с внешним (рис. 17.12).

Теорема 17.6. (Харари – Татт). Граф планарен тогда и только тогда, когда он не содержит подграфов, стягиваемых в K₅ или K_3,3.

Рис. 17.11. Граф Петерсона

Рис. 17.12. Граф K₅, полученный из графа Петерсона

Уитни связал планарность графов с существованием двойственных графов (ДГ). Для данного плоского графа G его геометрический ДГ, т.е. ГДГ G* строится так:

• поместим в каждую область G, включая внешнюю, по одной вершине G*;

• если две области имеют общее ребро u, соединим помещенные в них вершины ребром u*, пересекающим только u.

Данный процесс показан, например, для графа G (рис. 17.13).

Рис. 17.13. Пример построения ГДГ

Здесь ребра ГДГ G* штриховые линии. G* – имеет петлю, тогда когда в G есть концевая вершина в примере с рис. 3.10,в. G* – имеет кратные ребра, когда две области G содержат, по крайней мере, два общих ребра.

Таким образом, двусвязный плоский граф имеет всегда в качестве двойственного или граф, или мультиграф. ГДГ плоского графа G также плоский, а ГДГ к ГДГ – это первоначальный граф G.

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