27
правок
Изменения
Нет описания правки
{{Определение
|neat=neat
|definition=Граф<ref>На самом деле, ''двойственный граф'' — '''псевдограф''', поскольку в нём могут быть петли и кратные рёбра.</ref> <tex>G'</tex> называется 'G′'' называется двойственным'''(англ. 'двойственным'dual graph'' ) к [[Укладка графа на плоскости|планарному графу '']] <tex>G''</tex>, если:# Вершины ''<tex>G′'' </tex> соответствуют граням ''<tex>G''</tex>.# Между двумя вершинами в ''<tex>G′'' </tex> есть ребро тогда и только тогда, когда соответствующие грани в ''<tex>G'' </tex> имеют общее ребро.
}}
[[Файл:Dual_graphDual_graph_2.png|180px|thumb|right|Граф (белые вершины) и двойственный ему (полосатые серые вершины).]]
<div style='clear:left;'></div>
== Свойства ==
[[Файл:Treenflowernew.png|250px|thumb|right|Дерево и двойственный к нему «цветок».]]* Если ''<tex>G′'' </tex> — ''двойственный'' к двусвязному графу ''<tex>G''</tex>, то ''<tex>G'' </tex> — ''двойственный'' к ''<tex>G′''</tex>.* У одного и того же графа может быть несколько ''двойственных'', в зависимости от конкретной укладки (см. картинку).* Поскольку любой трёхсвязный планарный граф допускает только одну укладку на сфере<ref>''Харари, Ф.'' Теория графов. — М.: Книжный дом «ЛИБРОКОМ», 2009. — Теорема 11.5 — С. 130. — ISBN 978-5-397-00622-4.</ref>, у него должен быть единственный ''двойственный граф''.* [[Мост, эквивалентные определения|Мост ]] переходит в петлю, а петля — в мост. Частный случай: полный граф <tex>K_2</tex>* Мультиграф, ''двойственный'' к дереву, — цветок.
== Самодвойственные графы ==
{{Определение
}}
<div style='clear:left;'></div>
{{Утверждение
|neat=neat
|statement=<tex>K_1</tex> и <tex>K_4</tex> — самодвойственные графы. Среди полных графов других самодвойственных нет.
|proof=Проверить, что <tex>K_1</tex> и <tex>K_4</tex> полны и самодвойственны несложно. Докажем, что других нет.<br/>Поскольку грани графа переходят в рёбравершины, количество рёбер вершин и граней в исходном графе должно совпадать, т.е. <tex>V = F</tex>.<br/>Подставив в [[Формула Эйлера|формулу Эйлера]] имеем: <tex>2V = E + 2 \Leftrightarrow V = \fracdfrac{E}{2} + 1</tex>.<br/>В полном графе <tex>E = \fracdfrac{V \dot cdot (V - 1)}{2}</tex>.<br/>Получаем квадратное уравнение: <tex>V^2 - 5V + 4 = 0</tex>.<br/>Его решения: <tex>V_1 = 1</tex> и <tex>V_2 = 4</tex>.<br/>Таким образом, чтобы ''полный'' граф был ''самодвойственным'', в нём должна быть ровно '''одна''' или '''четыре''' вершины.
}}
|neat=neat
|statement=Все колёса самодвойственны.
|proof=Это утверждение очевидно. <br/>Достаточно посмотреть на убедиться, что два варианта укладки колеса (вершина с большой степенью внутри или вершина с большой степенью снаружи) и убедиться в том, что они двойственны друг другу.
}}
<div style="clear:both;"></div>
== См. также ==
*[[Формула Эйлера]]
*[[Укладка графа на плоскости]]
*[[Гамма-алгоритм]]
== Примечания ==
<references />
== Источники информации==
* [https://ru.wikipedia.org/wiki/%D0%94%D0%B2%D0%BE%D0%B9%D1%81%D1%82%D0%B2%D0%B5%D0%BD%D0%BD%D1%8B%D0%B9_%D0%B3%D1%80%D0%B0%D1%84 Википедия — Двойственный граф]
* [https://ru.wikipedia.org/wiki/%D0%9F%D0%BB%D0%B0%D0%BD%D0%B0%D1%80%D0%BD%D1%8B%D0%B9_%D0%B3%D1%80%D0%B0%D1%84 Википедия — Планарный граф]
[[Категория: Алгоритмы и структуры данных]]
[[Категория: Укладки графов]]