27
правок
Изменения
Нет описания правки
|neat=neat
|definition=Граф<ref>На самом деле, ''двойственный граф'' — '''псевдограф''', поскольку в нём могут быть петли и кратные рёбра.</ref> <tex>G'</tex> называется '''двойственным''' (англ. ''dual graph'') к [[Укладка графа на плоскости|планарному графу]] <tex>G</tex>, если:
# Вершины <tex>G'</tex> соответствуют граням <tex>G</tex>.# Между двумя вершинами в <tex>G'</tex> есть ребро тогда и только тогда, когда соответствующие грани в <tex>G</tex> имеют общее ребро.
}}
[[Файл:Dual_graph_2.png|180px|thumb|right|Граф (белые вершины) и двойственный ему (серые вершины).]]
== Свойства ==
[[Файл:Treenflower new.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>, у него должен быть единственный ''двойственный граф''.* [[Мост, эквивалентные определения|Мост]] переходит в петлю, а петля — в мост.* Мультиграф, ''двойственный'' к дереву, — цветок.
== Самодвойственные графы ==
{{Определение
|definition=Планарный граф называется '''самодвойственным'''(англ. ''self-dual graph''), если он изоморфен своему двойственному графу.
}}
<div style='clear:left;'></div>
