Двойственные графы

Рисунок 39

Для данного плоского графа G построим другой граф G*, называемый (геометрически) двойственным к G.Построение проводится в два этапа: (i) внутри каждой грани F_i графа G выбираем по одной точке v_i* — это вершины графа G*; (ii) каждому ребру е из G сопоставляем линию е*, пересекающую е (и никакое другое ребро графаG) и соединяющую те вершины v_i*, которые лежат в двух(не обязательно различных) гранях F_i смежных ребру е, —это ребра графа G*. Иллюстрацией этой процедуры служит рисунок 39, где вершины v_i* изображены крестиками, ребра е графа G — сплошными линиями, а ребра е* графа G* —пунктирными. Заметим, что висячая вершина в G порождает петлю в G* (так же, как и любой мост), и если две грани изG имеют больше одного общего ребра, то граф G* содержит кратные ребра.

Очевидно, что любые два графа, полученные таким образом из G, изоморфны; поэтому двойственный к G граф G*определен однозначно с точностью до изоморфизма. С другой стороны, стоит подчеркнуть, что изоморфность графовG и H не влечет за собой изоморфности G* и Н*.

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

Лемма 1. Пусть G — плоский связный граф с nвершинами, m ребрами и f гранями, и пусть G*— его геометрически двойственный граф, имеющий n* вершин, m*ребер и f* граней; тогда n* = f, m*=m и f* = n.

Доказательство. Первые два соотношения непосредственно вытекают из определения G*. Подставляя их в теорему Эйлера, примененную к обоим графам G и G*, получим третье соотношение. ▪

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

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

Доказательство. Достаточно заметить, что построение, при помощи которого G* получается из G, можно обратить и получить G из G*. Так, например, на рисунке 39 граф G является двойственным к G*. Остается только проверить, что грань графа G* не может содержать более одной вершины из G (одну-то она всегда содержит). Но это сразу следует
из соотношений n** = f* = n, где n* * — число вершин графа G**.▪

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

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

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

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

Доказательство. Без потери общности можно считать Gсвязным плоским графом. Если С — цикл в G, то С ограничивает одну или более конечных граней G и, следовательно, содержит внутри себя непустое множество S вершин графа G*. Отсюда сразу следует, что те ребра из G*, которые пересекают ребра цикла С, образуют разрез в G*, удаление которого разделяет G* на два подграфа. Множеством вершин одного из них является 5, другой же содержит те вершины, которые не принадлежат S (рисунок 40). Обратное утверждение доказывается простым обращением этого рассуждения. ▪

Следствие 1. Множество ребер графа G образует разрез в G тогда и только тогда, когда соответствующее множество ребер графа G* образует цикл в G*.

Доказательство. Применяя теорему 11 к графу G*и используя теорему 10, мы сразу получаем нужный результат. ▪

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

Рисунок 40

Рисунок 41

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

Из теоремы 11 ясно, что понятие абстрактной двойственности обобщает понятие геометрической двойственности: если G — планарный граф, a G* — геометрически двойственный к нему, то G* является и абстрактно двойственным к G. Теперь нам хотелось бы получить для абстрактно двойственных графов аналоги некоторых результатов, относящихся к геометрически двойственным графам. Ограничимся здесь одним из таких результатов — аналогом теоремы 10.

Теорема 12. Если граф G* абстрактно двойствен к графу G, то G абстрактно двойствен к G*.

Замечание. Отметим, что мы не требуем связности графа G.

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

С* должно быть либо отдельным циклом в G*, либо объединением двух или более реберно-непересекающихся циклов; но вторая возможность не имеет места, так как аналогичным образом можно показать, что циклы в G* соответствуют объединениям реберно-непересекающихся разрезов в G, и тогда С будет объединением двух или более реберно-непересекающихся разрезов, а не отдельным разрезом.▪

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

Теорема 13. Граф является планарным тогда и только тогда, когда он обладает абстрактно двойственным.

Замечание. Существует несколько доказательств этого результата. Здесь мы изложим одно особенно простое (принадлежащее Т. Д. Парсонсу)

Набросок доказательства. Как было замечено выше, достаточно доказать, что если граф G обладает абстрактно двойственным графом G*, то G планарен. Доказательство проводится в четыре этапа.

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

(ii) Далее устанавливаем, что если G обладает абстрактно двойственным графом, a G' гомеоморфен G, то G' также обладает абстрактно двойственным графом. Это следует из
того, что включение в G или удаление из G вершины степени 2 приводит к добавлению или вычеркиванию «кратного ребра» в G*.

(iii)Теперь надо показать, что ни К₅ ни K_{3, 3} не обладают абстрактно двойственными графами. Если граф G*является двойственным к К_{3, 3}. то, поскольку содержит только циклы длины четыре или шесть и не содержит разрезов, состоящих только из двух ребер, граф G* не содержит кратных ребер и степень каждой его вершины не меньше четырех. Поэтому граф G* обязан содержать по меньшей мере пять вершин и, следовательно, по меньшей мере½ *5*4=10 ребер, что невозможно. Рассуждение для К₅ проводится аналогично.

(iv) Предположим теперь, что G — непланарный граф, обладающий абстрактно двойственным графом G*. Тогда, по теореме Куратовского, граф G содержит подграф H, гомеоморфный К₅ илиК_{3, 3}. Как вытекает из (i) и (ii), подграф Н а потому K₅ или K_{3, 3}, должен обладать абстрактно двойственным графом, что противоречит (iii).