Представления о планарном графе

Плоский граф

Плоским графом называется граф, изображенный на плоскости так, что никакие два его ребра (или, вернее, представляющие их кривые) геометрически не пересекаются нигде, кроме инцидентной им обоим вершины. Граф, изоморфный плоскому графу, называется планарным. Планарный граф можно определить еще так: граф планарен, если его можно уложить на плоскости. Рисунок графа, в котором никакие два его ребра не пересекаются, если не считать точками пересечения общие вершины, называют плоским представлением графа. Ясно, что плоское представление имеет только плоский граф. Обратно, у всякого плоского графа непременно найдется плоское представление. Плоские графы — это простые циклы, деревья, лес, а также граф, содержащий цикл, из вершин которого "выходят" деревья.

Пример. Примером неплоского графа может служить полный граф с пятью вершинами. Любые попытки начертить его плоское представление обернутся неудачей.

В качестве характеристики плоского представления графа вводится понятие грани. Гранью в плоском представлении графа $$G$$ называется часть плоскости, ограниченная простым циклом и не содержащая внутри других циклов.

На рисунке показано плоское представление графа $$G$$ с тремя гранями: $$(1, 5, 4, 1)$$, $$(1, 3, 2, 4, 1)$$, $$(1, 2, 3, 1)$$. Часть плоскости, ограниченная простым циклом $$(1, 2, 4, 1)$$, гранью не является, так как содержит цикл $$(1, 2, 3, 1)$$. Простой цикл, ограничивающий грань, называется границей грани. Две грани будем называть соседними, если их границы имеют хотя бы одно общее ребро.

В данном графе часть плоскости, ограниченная простым циклом $$(1, 2, 3, 4, 1)$$, является гранью, так как ребро $$(4, 5)$$, расположенное внутри грани, не образует цикла.

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

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

Пример.

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

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

Пример.

Изображенные графы гомеоморфны, и то же самое можно сказать о любых двух циклических графах. Гомеоморфность графов является отношением эквивалентности. Ясно, что введение термина "гомеоморфны" удобно только с технической точки зрения — включение или удаление вершин степени 2 не имеет никакого отношения к планарности. Добавление (включение) одной вершины, скажем $$v$$, в какое-нибудь ребро, например $$e$$, осуществляется следующим образом: пусть ребро $$e$$ инцидентно вершинам $$w$$ и $$x$$. Тогда ребро $$e$$ удаляется из графа, но добавляются два новых ребра: $$e_{1}$$ инцидентное вершинам $$v$$ и $$w$$, и $$e_{2}$$, инцидентное вершинам $$v$$ и $$x$$.

Введение понятия гомеоморфности графов позволяет установить следующий важный результат, известный как теорема Куратовского (точнее, как теорема Понтрягина-Куратовского, так как Л.С.Понтрягин доказал, но не опубликовал, эту теорему еще в 1927 году), которая дает необходимое и достаточное условие планарности графа.

Гомеоморфные графы

Теорема (Куратовский, 1930) Граф планарен тогда и только тогда, если не содержит подграфов, гомеоморфных $$K_{5}$$ или $$K_{3,3}$$.

Поскольку доказательство теоремы Куратовского довольно длинное и сложное, здесь оно не приводится (см. Ф.Харари. Теория графов. М.: "Мир". 1973). Тем не менее, воспользуемся теоремой Куратовского для получения другого критерия планарности. Рассмотрим еще два определения. Элементарным стягиванием называется такая процедура: берем ребро $$e$$ (вместе с инцидентными ему вершинами, например, $$v$$ и $$w$$ ) и"стягиваем" его, то есть удаляем $$e$$ и отождествляем $$v$$ и $$w$$. Полученная при этом вершина инцидентна тем ребрам (отличным от $$e$$ ), которым первоначально были инцидентны $$v$$ или $$w$$.

Пример.

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

Граф планарен тогда и только тогда, если он не содержит подграфов, стягиваемых к $$K_{5}$$ или к $$K_{3,3}$$.

Формула Эйлера

Для всякого плоского представления связного плоского графа без перегородок число вершин ( $$V$$ ), число ребер ( $$E$$ ) и число граней с учетом бесконечной ( $$R$$ ) связаны соотношением $$V-E+R=2$$.

Пусть граф $$G$$ — связный, плоский граф без перегородок. Определим значение алгебраической суммы $$V - E + R$$ для его произвольного плоского представления.

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

Заметим, что при таком удалении одного ребра число граней уменьшается на $$1$$, так как при этом либо пропадет один простой цикл, либо два простых цикла преобразуются в один. Следовательно, значение разности $$E - R$$ при этом остается неизменным.

На рисунке ребра, которые мы удаляем, изображены кривыми. В полученном дереве обозначим число вершин — $$V_{d}$$, число ребер — $$E_{d}$$, число граней — $$R_{d}$$. Справедливо равенство $$E - R = E_{d} - R_{d}$$.

В дереве одна грань, то есть $$E - R = E_{d} - 1$$. Операция удаления ребер из графа не меняет число его вершин, то есть $$V = V_{d}$$. По теореме 2.1 (см. лекцию 2), в дереве $$V_{d} - E_{d} =1$$. Отсюда $$V - E_{d} =1$$, то есть $$E_{d} = V - 1$$, а потому $$E - R = V - 2$$ или $$V - E + R =2$$.

Итак, доказано, что если в плоском представлении связного графа без перегородок $$V$$ вершин, $$E$$ ребер и $$R$$ граней, то $$V - E + R =2$$. Полученная формула называется формулой Эйлера.

Пример.

Триангулированный граф

Рассмотрим плоский граф $$G$$ с пятью вершинами.

Если добавить к нему ребра $$(1,3)$$ и $$(1,5)$$, то полученный новый граф $$G$$ тоже будет плоским.

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

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

Каждая грань в плоском представлении максимально плоского графа имеет $$3$$ вершины. Поэтому максимально плоский граф называют триангулированным.

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

Задачи

Задача 1. На участке три дома и три колодца. От каждого дома к каждому колодцу ведет тропинка.

Граф G

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

Решение. Для решения задачи достаточно доказать, что граф $$G$$, изображенный на рисунке, не плоский.

Предположим, что граф $$G$$ — плоский, то есть существует его плоское представление. Граф $$G$$ — связный, он не имеет ни одного моста, поэтому не имеет и перегородок. По формуле Эйлера, $$V-E+R=2$$. Здесь $$V$$ — число вершин, $$E$$ — число ребер, $$R$$ — число граней с учетом бесконечной грани. Подсчитаем число вершин и ребер: $$V$$ = 6, $$E$$ = 9, поэтому $$R=2-6+9=5$$.

Теперь оценим удвоенное число ребер $$2E$$. Заметим, что в графе нет простых циклов длиной 3, то есть граница любой грани в плоском представлении графа $$G$$ содержит не менее четырех ребер. Заметим, что каждое ребро служит границей двух граней, так как мы учитываем и бесконечную грань. При этом число $$4R$$ не может быть больше удвоенного числа всех ребер: $$4R \le 2 E$$. Если бы мы знали число ребер в границе каждой грани, то их сумма должна быть равна $$2E$$ ; но известно, что $$2 E =18$$, а $$4 R =20$$, откуда $$20 \le 18$$. Полученное противоречие доказывает, что предположение было неверное, то есть граф $$G$$ — не плоский. Таким образом, намерения соседей неосуществимы.

Задача 2. Каждый из четырех соседей соединил свой дом с тремя другими дорожками, которые пересекались лишь около домов.

Граф G

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

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

Предположим, что граф $$G$$ плоский, то есть существует его плоское представление. Граф $$G$$ — связный, он не имеет перегородок, так как не имеет ни одного моста. Для плоского представления графа $$G$$ верна формула Эйлера. Подсчитаем число вершин и ребер: $$V =5$$, $$E = 10$$, тогда $$R = 2-5+10=7$$.

Оценим удвоенное число ребер $$2E$$. Каждая грань ограничена не более чем тремя ребрами (граф полный). Каждое ребро принадлежит границам двух граней, поэтому число $$3R$$ не может быть больше числа $$2E$$, то есть $$3R \le 2 E$$. Но $$2E =20$$, а $$3R =21$$, то есть $$20$$, $$20\ge 21$$. Противоречие доказывает, что предположение было неверным, то есть граф $$G$$ — не плоский.