7.5. Планарность и двойственность

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

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

Рис. 7.11. Построение двойственного графа.

Рассмотрим планарный граф.

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

1. G имеет вершин вершина v соответствует области .

2. G имеет столько же ребер, сколько и

3. Если ребро графа G является общим для областей (не обязательно различных), то соответствующее ребро графа G соединяет вершины . (Заметим, что каждое ребро графа G является общим, самое большее, для двух областей; возможно, что ребро лежит точно в одной области.)

Простой способ построения G заключается, во-первых, в размещении вершин в каждой области графа G. Затем для каждого ребра , общего для областей проводим линию, соединяющую вершины так чтобы она пересекала ребро Эта линия представляет ребро .

Процедура построения G иллюстрируется на рис. 7.11. Сплошные линии представляют собой ребра данного планарного графа G, а штриховые — ребра графа

Докажем, что граф G двойственный к графу

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

для построения графа G, следует, что ребра в инцидентны вершине v и образуют разрез, удаление которого отделит вершину v от остальных вершин графа

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

Теорема 7.12. Всякий планарный граф имеет двойственный к себе граф. Сразу же возникает вопрос: имеет ли непланарный граф двойственный к себе граф? Ответ на него отрицательный, и он основан на следующих двух леммах. Лемма 7.1. Граф не имеет двойственного графа.

Доказательство. Сначала заметим, что

1. Граф не имеет разрезающих множеств из двух ребер.

2. Граф имеет циклы длиной только четыре или шесть.

3. Граф имеет девять ребер.

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

1. Граф G не имеет циклов из двух ребер, т. е. он не имеет параллельных ребер.

2. Граф G не имеет разрезающих множеств с менее чем четырьмя ребрами. Таким образом, каждая вершина графа G имеет степень, не меньшую 4.

3. Граф G имеет девять ребер.

Из первых двух замечаний следует, что граф G имеет по крайней мере 5 вершин, каждая со степенью не менее 4. Таким образом, он должен иметь не менее ребер. Однако это противоречит замечанию 3. Следовательно, граф и не имеет двойственного графа.

Лемма 7.2. Граф не имеет двойственного графа.

Доказательство. Заметим сначала, что

1. Граф не имеет циклов длиной один или два.

2. Граф имеет разрезающие множества только из четырех или шести ребер.

3. Граф имеет десять ребер.

Допустим, граф имеет двойственный граф G. Тогда, согласно замечанию 2, граф G имеет циклы длиной только четыре или шесть. Другими словами, все циклы графа G имеют четную длину. Таким образом, G — двудольный граф. Поскольку двудольный граф с шестью или менее вершинами не может иметь больше девяти ребер, необходимо, чтобы граф G имел по крайней мере семь вершин. Однако, согласно замечанию 1, степень каждой вершины графа G не менее 3. Следовательно, граф G должен иметь по крайней мере ребер. Однако это противоречит замечанию 3. Следовательно, граф не имеет двойственного графа.

Основной результат этого раздела заключается в следующем:

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

Доказательство.

Достаточность устанавливается теоремой 7.12.

Необходимость можно доказать, показав, что непланарный граф G не имеет двойственного. По теореме Куратовского граф G содержит подграф Н, гомеоморфный графу или . Если бы граф G имел двойственный граф, тогда, согласно следствию 7.10.1, и подграф Н имел бы двойственный граф. Однако тогда по следствию 7.10.2 граф или должен был иметь двойственный. Однако это противоречит тому, что ни один из них не имеет двойственного графа. Следовательно, граф G не имеет двойственного графа.

Эта теорема характеризует планарные графы, исходя из существования

двойственных графов; впервые она была доказана Уитни. Используемое здесь доказательство предложил Парсонс [7.12]. Первоначальное доказательство Уитни, в котором не используется теорема Куратовского, можно найти в работе [7.13].

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

Теорема 7.14. Все двойственные графы графа 2 - изоморфны; любой граф, 2 - изоморфный двойственному графу G, также двойственный к графу G.

Доказательство этой теоремы непосредственно вытекает из определения двойственного графа и теоремы 1.7.