27
правок
Изменения
Нет описания правки
Чтобы для данного плоского графа <tex>G</tex> построить двойственный <tex>G'</tex>, необходимо поместить по вершине <tex>G'</tex> в каждую грань <tex>G</tex> (включая внешнюю), а затем, если две грани в <tex>G</tex> имеют общее ребро, соединить ребром соответствующие им вершины в <tex>G'</tex> (если грани имеют несколько общих рёбер, соответствующие вершины следует соединить несколькими параллельными рёбрами). В результате всегда получится плоский псевдограф.
Например, существуют графы, двойственные себе: тетраэдр — самодвойственный граф, куб <tex>K_1</tex> и октаэдр — двойственные<tex>K_4</tex>. Далее мы убедимся, так же как додекаэдр и икосаэдр. Эти пять что среди полных графов, образованные вершинами и рёбрами правильных многогранников, называют ''платоновыми''только они обладают таким свойством.
* У одного и того же графа может быть несколько ''двойственных'', в зависимости от конкретной укладки (см. картинку).
* Поскольку любой трёхсвязный планарный граф допускает только одну укладку на сфере<ref>Харари, Ф. Теория графов. — М.: Книжный дом «ЛИБРОКОМ», 2009. — Теорема 11.5 — С. 130. — ISBN 978-5-397-00622-4</ref>, у него должен быть единственный ''двойственный граф''.
* [[Мост, эквивалентные определения|Мост]] переходит в петлю, а петля — в мост.Частный случай: полный граф <tex>K_2</tex>
* Мультиграф, ''двойственный'' к дереву, — цветок.
