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

Материал из Викиконспекты
Перейти к: навигация, поиск
НЕТ ВОЙНЕ

24 февраля 2022 года российское руководство во главе с Владимиром Путиным развязало агрессивную войну против Украины. В глазах всего мира это военное преступление совершено от лица всей страны, всех россиян.

Будучи гражданами Российской Федерации, мы против своей воли оказались ответственными за нарушение международного права, военное вторжение и массовую гибель людей. Чудовищность совершенного преступления не оставляет возможности промолчать или ограничиться пассивным несогласием.

Мы убеждены в абсолютной ценности человеческой жизни, в незыблемости прав и свобод личности. Режим Путина — угроза этим ценностям. Наша задача — обьединить все силы для сопротивления ей.

Эту войну начали не россияне, а обезумевший диктатор. И наш гражданский долг — сделать всё, чтобы её остановить.

Антивоенный комитет России

Распространяйте правду о текущих событиях, оберегайте от пропаганды своих друзей и близких. Изменение общественного восприятия войны - ключ к её завершению.
meduza.io, Популярная политика, Новая газета, zona.media, Майкл Наки.


Определение:
Граф[1] [math]G'[/math] называется двойственным (англ. dual graph) к планарному графу [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] (если грани имеют несколько общих рёбер, соответствующие вершины следует соединить несколькими параллельными рёбрами). В результате всегда получится плоский псевдограф.

Например, существуют графы, двойственные себе: — [math]K_1[/math] и [math]K_4[/math]. Далее мы убедимся, что среди полных графов только они обладают таким свойством.


Свойства

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


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

Определение:
Планарный граф называется самодвойственным (англ. self-dual graph), если он изоморфен своему двойственному графу.


Колесо и двойственный ему граф — тоже колесо.
[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 = \dfrac{E}{2} + 1[/math].
В полном графе [math]E = \dfrac{V \cdot (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]

См. также

Примечания

  1. На самом деле, двойственный графпсевдограф, поскольку в нём могут быть петли и кратные рёбра.
  2. Харари, Ф. Теория графов. — М.: Книжный дом «ЛИБРОКОМ», 2009. — Теорема 11.5 — С. 130. — ISBN 978­-5­-397­-00622­-4

Источники информации