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

Определение:

Граф [math]G'[/math] называется двойственным к планарному графу [math]G[/math], если:

1. Вершины [math]G'[/math] соответствуют граням [math]G[/math]
2. Между двумя вершинами в [math]G'[/math] есть ребро тогда и только тогда, когда соответствующие грани в [math]G[/math] имеют общее ребро

Граф (белые вершины) и двойственный ему (полосатые вершины).

Чтобы для данного плоского графа [math]G[/math] построить двойственный [math]G'[/math], необходимо поместить по вершине [math]G'[/math] в каждую грань [math]G[/math] (включая внешнюю), а затем, если две грани в [math]G[/math] имеют общее ребро, соединить ребром соответствующие им вершины в [math]G'[/math] (если грани имеют несколько общих рёбер, соответствующие вершины следует соединить несколькими параллельными рёбрами). В результате всегда получится плоский псевдограф.

Например: тетраэдр — самодвойственный граф, куб и октаэдр — двойственные, так же как додекаэдр и икосаэдр. Эти пять графов, образованные вершинами и рёбрами правильных многогранников, называют платоновыми.

В верхнем двойственном графе есть вершина степени 6, а в нижнем — нет. Следовательно, они не изоморфны.

Свойства

Дерево и двойственный к нему «цветок».‎

• Если [math]G'[/math] — двойственный к двусвязному графу [math]G[/math], то [math]G[/math] — двойственный к [math]G'[/math]
• У одного и того же графа может быть несколько двойственных, в зависимости от конкретной укладки (см. картинку)
• Поскольку любой трёхсвязный планарный граф допускает только одну укладку на сфере, у него должен быть единственный двойственный граф
• Мост переходит в петлю, а петля — в мост
• Мультиграф, двойственный к дереву, — цветок

Самодвойственные графы

Определение:

Планарный граф называется самодвойственным, если он изоморфен своему двойственному графу.

Колесо и двойственный ему граф — тоже колесо.

[math]K_4[/math] (он же колесо).

Утверждение:

[math]K_1[/math] и [math]K_4[/math] — самодвойственные графы. Среди полных графов других самодвойственных нет.

[math]\triangleright[/math]

Проверить, что [math]K_1[/math] и [math]K_4[/math] полны и самодвойственны несложно. Докажем, что других нет.
Поскольку грани графа переходят в вершины, количество вершин и граней в исходном графе должно совпадать, т.е. [math]V = F[/math].
Подставив в формулу Эйлера имеем: [math]2V = E + 2 \Leftrightarrow V = \frac{E}{2} + 1[/math].
В полном графе [math]E = \frac{V \dot (V - 1)}{2}[/math].
Получаем квадратное уравнение: [math]V^2 - 5V + 4 = 0[/math].
Его решения: [math]V_1 = 1[/math] и [math]V_2 = 4[/math].
Таким образом, чтобы полный граф был самодвойственным, в нём должна быть ровно одна или четыре вершины.

[math]\triangleleft[/math]

Утверждение:

Все колёса самодвойственны.

[math]\triangleright[/math]

Это утверждение очевидно.
Достаточно убедиться, что два варианта укладки колеса (вершина с большой степенью внутри или вершина с большой степенью снаружи) двойственны друг другу.

[math]\triangleleft[/math]