Изменения
Нет описания правки
{{Определение
|neat=neat
|definition=Граф<ref>На самом деле, ''двойственный граф'' — '''псевдограф''', поскольку в нём могут быть петли и кратные рёбра.</ref> ''<tex>G′'' </tex> называется '''двойственным''' к планарному графу ''<tex>G''</tex>, если:# Вершины ''<tex>G′'' </tex> соответствуют граням ''<tex>G''</tex># Между двумя вершинами в ''G′'' есть ребро тогда и только тогда, когда соответствующие грани в ''<tex>G'' </tex> имеют общее ребро
}}
[[Файл:Dual_graph.png|thumb|right|Граф (белые вершины) и двойственный ему (полосатые вершины).]]
Чтобы для данного плоского графа ''<tex>G'' </tex> построить двойственный ''<tex>G′''</tex>, необходимо поместить по вершине ''<tex>G′'' </tex> в каждую грань ''<tex>G'' </tex> (включая внешнюю), а затем, если две грани в ''<tex>G'' </tex> имеют общее ребро, соединить ребром соответствующие им вершины в ''<tex>G′'' </tex> (если грани имеют несколько общих рёбер, соответствующие вершины следует соединить несколькими параллельными рёбрами). В результате всегда получится плоский псевдограф.
Например: тетраэдр — самодвойственный граф, куб и октаэдр — двойственные, так же как додекаэдр и икосаэдр. Эти пять графов, образованные вершинами и рёбрами правильных многогранников, называют ''платоновыми''.
== Свойства ==
[[Файл:Treenflower.png|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>, у него должен быть единственный ''двойственный граф''
