Тексты лекций / Текст лекции 11

§ 3.4. Планарность

Укладки графавпространствеинаплоскости.Планарныеграфы.Плоскиеграфы. Грани плоского графа. Связь между числом вершин, ребер и граней плоского графа, формула Эйлера. Критерии планарности.

Базовые понятия и утверждения

1.Укладка графа в трехмерном пространстве. Говорят, что граф обладает укладкой

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

Пример 1. Рассмотрим граф свершинами , , , и ребрами = , = , =, = , = , = .

Укладка данного графа в пространстве изображена на рис. 3.48.

Утверждение. Любой граф обладает укладкой в пространстве.

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

Возьмем в пространстве любую прямую (рис. 3.49). Вершинам графа поставим в соответствие точки прямой так, чтобы каждой вершине соответствовала своя точка; каждую точку пометим именем сопоставленной ей вершины.

Через прямую проведем столько плоскостей, сколько ребер у графа (каждому ребру будет соответствовать своя плоскость). Если ребро = не является петлей, то изобразим его в соответствующей ему плоскости в виде полуокружности с диаметром [ ,]. Если ребро = - петля, то изобразим его в соответствующей ему плоскости в виде окружности, которая касается прямой в точке .

Очевидно, построенная таким образом диаграмма будет укладкой графа в трехмерном пространстве. ■

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

На рис. 3.50 изображена укладка на плоскости графа из примера 1.

Далеемыубедимсявтом,чтоневсеграфыимеютплоскуюукладку.Граф,обладающий укладкой на плоскости, называют планарным. Любую укладку планарного графа на плоскости называют плоским графом.

1

Например, граф из примера 1 - планарный, а его диаграмма на рис. 3.50 - плоский граф.

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

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

Например, плоский граф, изображенный на рис. 3.51, имеет четыре грани: три внутренние ( , , ) и одну внешнюю ( ). Любое дерево имеет только одну грань - внешнюю.

a e3 c S1S2S3

bS4

Рис. 3.50. Рис. 3.51.

Справедливо следующее утверждение.

Пусть = ( , ) - связный плоский граф, - множество его граней. Тогда | | = | | − | |+ 2 (формула Эйлера).

Доказательство утверждения приведено во второй части параграфа.

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

Пример 2. Доказать, что полный граф непланарен.

◄ Будемрассуждать от противного. Предположим, что граф (см.рис.3.7) планарен. Тогда унего есть укладканаплоскости.Пусть -множество гранейэтойукладкии граница i-йгранисостоитиз ребер,где = 1,...,| |.Посколькукаждоеребрографа содержится в некотором цикле и, следовательно, лежит на границе двух граней, то

+ +...+ | | = 2| |.

Граф не имеет петель и кратных ребер, значит, каждая грань его укладки граничит

Граф имеет 5 вершин и 10 ребер, следовательно, по формуле Эйлера | | = | | − | |+ 2 = 10− 5+2 = 7. Значит, должно выполняться неравенство 21 ≤ 20, что неверно. Пришли к противоречию. Следовательно, предположение о планарности графа было неверным. ►

Пример 3. Доказать, что полный двудольный граф , непланарен.

◄ Будем рассуждать от противного. Предположим, что граф , (см. рис. 3.8) планарен. Пусть - множество граней этой укладки и граница i-й грани состоит из ребер, где= 1,...,| |. Поскольку каждое ребро графа , содержится в некотором цикле и, следовательно, лежит на границе двух граней, то

+ +...+ | | = 2| |.

Несложно убедиться, что в графе , все простые циклы имеют длину, не меньшую 4,

т.е. ≥ 4 ( = 1,...,| |), и, значит, 4| | ≤ 2| |, откуда 2| | ≤ | |. С учетом того, что граф

2

Тема 11. «Планарность» Олейник Т.А., 2020

, имеет 6 вершин и 9 ребер по формуле Эйлера получим | | = | |− | | +2 = 9 − 6+ 2 = 5, значит, должно выполняться неравенство 2 5 ≤ 9. Пришли к противоречию. Следовательно, предположение о планарности графа , было неверным. ►

Упражнение 3.24. а) Одной из диаграмм графа является трехмерный куб (рис. 3.52,а). Планарен ли данный граф?

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

аб

Рис. 3.52.

Упражнение 3.25. а) Одной из диаграмм графа является октаэдр (рис. 3.53,а). Планарен ли данный граф?

б) Одной из диаграмм графа является октаэдр, в котором проведена диагональ (рис. 3.53,б). Планарен ли данный граф?

а б

Рис. 3.53.

Теоретические обоснования

Теорема 3.5 (о плоских графах). Пусть = ( ,) - плоский граф, - множество его граней. Тогда

| | − | |+ ( ) = | |− 1.

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

Базис индукции. Пусть | | = 0, т.е. граф не имеет ребер. Тогда | | = ( ), | | = 1, поэтому доказываемая формула справедлива.

Индуктивный переход. Предположим, что формула верна для любого графа с числом ребер, меньшим либо равным . Покажем, что она остается в силе для графа , число реберкоторогоравно + 1.Возьмемкакое-нибудьребро графа и удалимего.Получим граф − ,числореберкоторогоравно .Тогдадляплоскойукладкиграфа справедливо предположение индукции и, значит, выполняется равенство

|( − )|− |( − )| + |( − )| = |( − )|− 1.

Рассмотрим два случая: 1) удаленное ребро - не мост и 2) удаленное ребро - мост.

1. Пусть удаленное ребро - не мост. Тогда содержится в некотором цикле графа и поэтому лежит на границе двух граней его плоской укладки. Если удалить из графа ребро, то эти две грани сольютсяв одну и числограней в плоской укладке графа − окажется на единицу меньшим числа граней в плоской укладке графа , т.е. |( − )| = |( )|− 1.

3

Следовательно, равенство

|( − )| − |( − )|+ |( − )| = |( − )|− 1

можно переписать в виде

(|( )| − 1) − |( )|+ |( )| = (|( )| − 1) − 1

или

|( )|− |( )|+ |( )| = |( )| − 1.

2. Пусть теперь удаленное ребро - мост. Тогда не содержится ни в одном цикле графа и поэтому не входит в границы граней плоской укладки этого графа. Значит, ни одна из граней графа не пострадает при его удалении, так что |( − )| = |( )|. Из того, что - мост следует также, что |( − )| = |( )|+ 1. Кроме того, |( − )| = |( )|− 1, |( − )| = |( )|.

Следовательно, равенство

|( − )| − |( − )|+ |( − )| = |( − )|− 1

можно переписать в виде

(|( )|− 1) − |( )|+ (|( )| + 1) = |( )| − 1,

или

|( )|− |( )| + |( )| = |( )| −1.

Таким образом, в обоих случаях индуктивный переход доказан. ■ Заметим, что поскольку | |− | | + ( ) = ( ), то из теоремы следует, что цикло-

матическое число плоского графа равно числу его внутренних граней.

Следствие. В частном случае связного плоского графа из равенства | | − | |+ ( ) = | |− 1 получаем формулу Эйлера | | = | |− | |+ 2.

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

Операция, обратная операции включения вершины степени 2, называется исключением вершины степени 2.

Будем говорить, что граф гомеоморфен графу , если изоморфен некоторому графу, который можно получить из путем применения конечное число раз операций включения и исключения вершин степени 2.

Пример 4. Графы , и (рис.3.54)-попарногомеоморфны.Действительно, графможно получить из графа путем исключения вершины (и наоборот, граф можно получить из графа путем включения вершины ). Граф можно получить из графа путем включения вершины (и наоборот, граф можно получить из графа путем ис-

4

Приведем без доказательства один из критериев планарности.

Теорема 3.6 (Понтрягина и Куратовского). Граф планарен тогда и только тогда,

когда у него нет подграфов, гомеоморфных , и нет подграфов, гомеоморфных , .

Пример 5. На рис. 3.55 изображены граф Петерсена и его подграф .

(на рис. 3.55 соответствующие вершины помечены одинаковыми числами), аграф гомеоморфенграфу , .Такимобразом,графПетерсенанепланарен.Заметим,чтопри этомграф Петерсена не содержит подграфов, гомеоморфных .

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

Пример 6. На рис. 3.56 показан пример применения операции стягивания ребра: графполучен из графа стягиванием ребра .

Рис. 3.56.

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

Приведем без доказательства еще один критерий планарности.

Теорема 3.7 (Вагнера, Харари и Татта). Граф планарен тогда и только тогда, когда у него нет подграфов, стягиваемых к , и нет подграфов, стягиваемых к , .

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

цами 1 и 5, 6 и 9, 2 и 7, 4 и 8, 3 и 10 (см. рис. 3.55).

Задачи повышенной сложности

3.24. Рассмотрим на множестве графов бинарное отношение гомеоморфизма (пара графов и связана этим отношением, если гомеоморфен ). Какими свойствами это бинарное отношение обладает?

3.25. Какие из графов, изображенных на рис. 3.57 - 3.59, являются планарными?

5

Рис. 3.57. Рис. 3.58. Рис. 3.59.

3.26. При каких граф, изображенный на рис. 3.60, является планарным? 3.27. При каких граф, изображенный на рис. 3.61, является планарным?

3.29. Доказать, что граф непланарен.

Ответы и указания к упражнениям

3.24. а) Планарен. Исходная и плоская укладки графа представлены на рис. 8 (соответствующие вершины помечены одинаковыми буквами).

b1 c1 b1c1

Рис. 8.

б) Непланарен. Решение. Будем рассуждать от противного. Предположим, что граф планарен. Тогда у него есть укладка на плоскости. Пусть - множество граней этой укладки и граница i-й грани состоит из ребер, где = 1,...,| |. Поскольку каждое ребро графа содержится в некотором цикле и, следовательно, лежит на границе двух граней, то ++...+ | | = 2| |. Несложно убедиться, что в графе все простые циклы имеют длину ≥ 4 ( = 1,...,| |). Следовательно, 4| | ≤ 2| |, т.е. 2| | ≤ | |. Учитывая, что граф имеет 8

вершин и13ребер,поформулеЭйлераполучаем | | = | | − | |+ 2 = 13− 8 + 2 = 7.Значит, должно выполняться неравенство 2 7 ≤ 13, что неверно. 3.25. а) Исходная и плоская укладки графа представленына рис. 9(соответствующие вершиныпомечены одинаковыми числами); б) непланарен.

55

4 3 43

Рис. 9.

6