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

Утверждение 4.1. Если G — плоский связный (n, т)-граф с f гранями, a G* — (n*, т*)-граф, геометрисески двойственный к нему, с I* гранями, то n* = f, n* = m, f* = n.

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

Теорема 4.1. Если G — плоский связный граф, то граф G** изоморфен графу G.

Из утверждения 4.1 следует, что n** —f* = n, где n**=\G**\. Следовательно, каждая грань графа G* со­держит одну вершину графа G (G**). Поэтому построе­ние, при помощи которого граф G* получен из G, можно обратить, т. е. получить G из G*.

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

Теорема 4.2. Пусть G —планарный граф, G* — граф, геометрически двойственный к G. Подмножество ребер из G образует простой цикл в G тогда и только тогда, когда соответствующее множество ребер из G* об­разует разрез в G*.

Для доказательства этой теоремы потребуется одна очевидная лемма.

Лемма 4.2. Пусть Н — связный граф, множество VH вершин которого разбито на два подмножества V1 и V2. Множество ребер

является разрезом тогда и только тогда, когда графы H(V1) u H(V2) связны.

Доказательство теоремы 4.2. Не исклю­чая общности, будем считать, что G — плоский граф.

Пусть С — простой цикл в G. Тогда он ограничивает одну или несколько внутренних граней графа G, т. е. ог­раничивает часть плоскости, содержащую непустое мно­жество W вершин графа G*. Поэтому ребра из G*, пере­секающие ребра цикла С, образуют множество М в G*, удаление которого разделяет связный граф G* на два подграфа с множествами вершин W и VG*\W (рис. 40.3). Индукцией по числу вершин легко доказать связность каждого из этих подграфов. Следовательно, на основании леммы 40.4 М — разрез в графе G*.

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

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

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

На рис. 40.4 изображены граф и абстрактно двойственный к нему граф. Соответствующие ребра обо­значены одной и той же буквой.

Понятие абстрактной двойственности обобщает понятиe геометрической двойственности, так как согласно теореме 40.3 справедливо

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

Непосредственно из определения вытекает следующее утверждение.

Утверждение 4.4. Граф Н является абстрактно двойственным к графу G тогда и только тогда, когда матроид M(G) циклов графа G изоморфен матроиду М*(G) разрезов графа Н.

5. Алгоритм укладки графа на плоскости

Рассмотренные в предыдущих параграфах критерии планарности таковы, что если даже удалось установить планарность графа, то нет информации о том, как строить его укладку на плоскости. В то же время при реше­нии практических задач недостаточно знать, что граф планарен, а необходимо, как правило, построить его плоское изображение. Все это вызвало появление алгоритмов, которые не только проверяют граф на планарность, но и одновремен­но строят его плоскую укладку, если это возможно. Один из таких алгоритмов (алгоритм γ ) рассмотрим в этом параграфе.

Алгоритм γ укладки графа G представляет собой процесс последовательного присоединения к некоторому уложенному подграфу С0 графа G новой цепи, оба конца ко­торой принадлежат G0. Тем самым эта цепь разбивает одну из граней графа G0 на две. При этом в качестве на­чального плоского графа G0 выбирается любой простой цикл графа G. Процесс продолжается до тех пор, пока не будет построен плоский граф, изоморфный графу G, или присоединение некоторой цепи окажется невозможным. В последнем случае граф G не является планарным.

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

Введем ряд определений. Пусть построена некоторая укладка подграфа G0 графа G. Сегментом S относительно G0 (иногда просто сегментом) будем называть подграф графа G одного из следующих двух видов:

ребро e = uvEG такое, что eи  EG0,  u,vVG0;

связную  компоненту  графа  G — G0, дополненную
всеми ребрами графа G, инцидентными вершинам взя­той компоненты, и концами этих ребер.

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

Вершину v сегмента S относительно G0 будем называть контактной, если v  VG0. Так как в графе G нет то­чек сочленения, то легко доказать, что в случае, когда граф G является 2-связным, каждый сегмент содержит не менее двух контактных вершин.

На рис. 41.1 изображены граф G, его уложенный под­граф G0 и все сегменты относительно G0. Контактные вер­шины сегментов обведены кружками.

Поскольку граф G0 плоский, то он разбивает плоскость нa грани. Допустимой гранью для сегмента S относительно G0 называется грань Г графа G0, содержащая все контактные вершины сегмента S. Через Г(S) будем обозначать множество допустимых граней для S. Может оказаться, что Г (S) = ø.

Простую цепь L сегмента S, соединяющую две различные контактные вершины и не содержащую других контактных вершин, назовем α-цепью. Очевидно, что всякая α-цепь, принадлежащая сегменту, может быть уло­жена в любую грань, допустимую для этого сегмента.

Два сегмента S1 и S2 относительно G назовем конфликтующими если

0 = Г (S1)  Г (S2)  ø, 2) существуют две α -цепи L1 S1, L2 S2, которые без пересечений нельзя уложить одновременно ни в какую грань Г  0. В противном случае будем говорить, что сегменты не конфликтуют.

Для графа, изображенного на рис. 41.1, конфликтую­щими являются, например, сегменты S1 и S2, S3 и S4,S2 и S6

Вернемся к обсуждению алгоритма у.

Итак, на первом шаге этого алгоритма уложим про­извольный простой цикл графа G.

Пусть, далее, G0 — построенная на предыдущем шаге укладка некоторого подграфа графа G. Для каждого сегмента относительно G0 находим множество допустимых граней. Теперь могут представиться только следующие три случая.

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

2.      Для некоторого сегмента S существует единствен­ная допустимая грань Г. Тогда очередной шаг состоит в расположении любой α -цепи сегмента S в грани Г. При этом, как уже отмечалось, а-цепь разбивает грань Г на две грани.

3.      Г (S)2 для всякого сегмента S. Тогда появляется несколько вариантов продолжения построения укладки графа, поскольку любой сегмент можно размещать в лю­бую допустимую для этого сегмента грань. Поэтому возникают опасения, что неудачный выбор сегмента и грани может помешать процессу построения укладки на следующих шагах и плоская укладка планарного графа не будет построена. Это могло бы привести нас к невер­ному заключению о том, что планарный граф непланарен. В дальнейшем мы покажем, что в этом случае для про­должения алгоритма γ можно выбирать цепь в любом сегменте и помещать ее в любую допустимую грань.

Формально опишем алгоритм γ.

1.      Выберем некоторый простой цикл С графа G и уложим его на плоскости; положим G0 = =C.             

2.      Найдем грани графа G0 и сегменты относительно G0. Если множество сегментов пусто, то перейдем к п. 8.

3.      Для каждого сегмента  S  определим  множество Г(S).             

4.      Если существует сегмент S, для которого Г (S) = ø, то граф G непланарен. Конец. Иначе перейдем к п. 5.             

5.      Если существует сегмент S, для которого имеется единственная допустимая грань Г, то перейдем к п. 7. Иначе — к п. 6.             

6.      Для некоторого  сегмента S (Г(S)> 1)  выбираем произвольную допустимую грань Г.             

7.      Поместим произвольную а-цепь L  S в грань Гзаменим G0 наG U L и перейдем к п 2.  

Построена укладка G0 графа G на плоскости. Конец.
Шагом алгоритма γ будем считать присоединение к G α -цепи L.

6. Характеристики планарных графов

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

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

Графы, которые нельзя уложить на плоскости, но можно уложить на торе, называются тороидальными. На рис. 42.3 изображена укладка графа Кз,з на торе. Утвердительный ответ на этот вопрос получаем сразу же, если нарисуем граф на плоскости и для каждого пе­ресечения двух ребер, добавив к плоскости ручку, прове­дем одно ребро по ручке, а другое — под ней. На рис. 42.1 изображена укладка графа К5 на плоскости, к которой добавлена одна ручка, т. е. построен «мост». Тем самым очевидно, что граф К5 (и Кз,з) можно уложить на торе, т. е. на сфере с одной ручкой(рис 42.2).

Укладку тороидального графа на торе удобно изобра­зить с помощью прямоугольника, в котором отождествле­ны обе пары противоположных сторон. На рис. 42.4—42.7 изображены такие укладки тороидальных графов К5, Gз,з, К7, K4,4 соответственно.

Определим теперь род Y(G) графа G как наименьшее число ручек, которые необходимо добавить к сфере, что­бы можно было граф G уложить на полученной таким образом поверхности. Тем самым, поскольку графы К5 Кз,з, K7,K4,4 непла-
нарны, то y(K5) = Y(K3,3) = Y (K7) = Y(К4,4)=1. Тогда:

1) Y(G) = 0 тогда и только тогда, когда граф G планарный;

2) Y(G)=1 тогда и только тогда, когда граф G тороидальный.

Числом скрещиваний cr(G) графа  G называется  наименьшее число пересечений, получаемых при изображении графа на плоскости (поня­тие пересечения относится к пересечению ровно двух ребер). Очевидно, что сг(С) = 0 тогда и только тогда, когдa G — планарный граф. Приведем здесь следующие известные оценки для числа скрещиваний

где Qn — n-мерный куб

При изготовлении печатных схем соединительные провода наносятся на одну сторону непроводящей пластинки. Поскольку печатные проводники нe изолированы, то они не должны пересекаться. Поэтомy важно знать, является ли планарным граф, в котором роль вершин играют приборы, а ребрами являются соединения. Таким образом,  мы приходим к понятию толщины графа. Толщиной t(G)  графа G называется наименьшее число его планарных подграфов, объединение которых дает граф G. Толщина планарного графа равна 1. Для толщины связного (n, m)-графа справедливы оценки

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

7. упражнения

Задача 7.1. На участке 3 дома и 3 колодца. От каждого дома к каждому колодцу ведет тропинка (рис. 2.13). Когда владельцы  домов поссорились, они задумали проложить дороги от каждого дома к каждому колодцу так, чтобы не встречаться на пути к колодцам.

Покажите, что их намерения не могли осуществиться.

Решение. Для решения задачи достаточно доказать, что граф Г, изображенный на рисунке 2.13, не плоский. Предположим, что граф Г — плоский, т. е. существует его плоское  представление. Граф Г — связный, он не имеет ни одного моста, поэтому не имеет и перегородок.

По формуле Эйлера:

в — р + г = 2. Подсчитаем число вершин и ребер: в = 6, р = 9, поэтому г = 2 — 6 + 9 = 5.

Теперь оценим удвоенное число ребер 2р. Заметим, что в графе на рисунке 2.13 нет простых циклов длиной 3, т. е. граница любой  грани в плоском представлении графа Г содержит не менее четырех  ребер. Заметим, что каждое ребро служит границей двух граней,  так как мы учитываем и бесконечную грань. При этом число 4г  не может быть больше удвоенного числа всех ребер:

4г ≤ 2р. Если бы мы знали число ребер в границе каждой грани, то их сумма  должна быть равна 2р; но известно, что 2р = 18, а 4г = 20, откуда 20 ≤ 18. Полученное противоречие доказывает, что  предположение было неверное, т. е. граф Г на рисунке 2.13 не плоский.  Намерения соседей неосуществимы.

Задача 7.2. Каждый из четырех соседей соединил свой дом с тремя другими дорожками, которые пересекались лишь около домов (рис. 2.14). Докажите, что дом пятого соседа со всеми остальными домами соединить непересекающимися дорожками  невозможно, т. е. он вынужден построить мост или рыть подземный ход. Решение задачи сводится к доказательству того, что полный граф Г с пятью вершинами (рис. 2.15) не является плоским.