§ 3.4. Планарные графы
Граф
называется планарным,
если он имеет плоскую
укладку,
т.е. такое изображение на плоскости, при
котором рёбра графа не имеют общих
внутренних точек. Например, граф
планарен (см. рис. 3.30). Граф
также планарен (см. рис. 3.26).
Однако, существуют и непланарные графы. Условия планарности графа будут рассмотрены позже.
С
вязный
планарный граф, если его изобразить на
плоскости без самопересечения рёбер,
будет определять некоторую карту,
которая состоит из областей, на которые
разбивают плоскость рёбра графа (при
этом вершины и рёбра, не входящие ни в
один цикл, игнорируются). Эти области
мы будем называть гранями
(так как часто карта является развёрткой
многогранника) или странами
(см. рис. 3.31).
Одна из стран
неограниченная – её называют океаном.
На рисунке 31
– ограниченные страны,
– океан.
Пусть
– количество граней в данной плоской
укладке планарного графа. Тогда
справедлива формула
Эйлера:
(7)
Равенство (7) верно и для планарных графов с кратными рёбрами.
Для данной плоской
укладки планарного графа обозначим
через
количество
-угольных
граней (
).
То есть
– количество двуугольников (они могут
присутствовать у графа с кратными
рёбрами),
– количество треугольников,
– четырёхугольников и т.д. в плоской
укладке. Тогда имеют место соотношения
(8)
С помощью этих соотношений можно доказывать непланарность графов.
Упражнение 3.24.
Доказать, что граф
не планарен.
Решение.
Предположим, что граф
планарен. Рассмотрим какую-либо его
плоскую укладку. Пусть
– количество граней в плоской укладке.
Ясно, что у графа
и
По формуле (7) получаем:
откуда
Подставим эти цифры в соотношение (8_).
Получим:
Заметим, что
так как у графа
нет кратных рёбер. Кроме того,
так как граф
не имеет циклов длины 3. Поэтому получаем:
В
ычтем
из второго уравнения первое, умноженное
на 4, получим:
Но это равенство невозможно, так как
все
Таким образом, граф
не планарен.
Операцией
разделения ребра
графа
будем называть переход от графа
к графу
который получается из графа
добавлением вершины
и заменой ребра
двумя рёбрами
и
(см. рис. 3.32).
Графы
и
называются гомеоморфными,
если из графа
применением несколько раз операции
разделения ребра можно получить некоторый
граф
а из графа
– граф
такие, что
Гомеоморфизм графов – более слабое
условие, чем изоморфизм (любые два
изоморфных графа гомеоморфны, но не
наоборот). Например, графы
и
гомеоморфны друг другу, но не изоморфны.
Необходимое и достаточное условие
планарности графа даёт следующая
теорема.
Теорема Понтрягина
– Куратовского. Граф
планарен в том и только том случае, если
у него нет подграфов, гомеоморфных графу
или графу
Упражнение 3.25.
Показать с помощью теоремы Понтрягина
– Куратовского, что граф
не планарен.
Р
ешение.
Граф
образно называют “три дома – три
колодца” (см. рис. 3.33).Это название
возникло от старинной задачи: даны 3
дома и 3 колодца; можно ли от каждого
дома к каждому колодцу провести дорожку
так, чтобы эти дорожки не пересекались?
Непланарность графа
доказывает несуществование дорожек,
удовлетворяющих условиям задачи.
Н
епланарность
графа
(это 4-мерный куб, см. рис. 3.7) будет
доказана, если мы найдём у него подграф,
гомеоморфный графу
Это делается несложно, решение можно
увидеть на рисунке 3.34.