Двойственный граф планарного графа — различия между версиями
Kirelagin (обсуждение | вклад) (фикс) |
|||
| Строка 4: | Строка 4: | ||
{{Определение | {{Определение | ||
|neat=neat | |neat=neat | ||
| − | |definition=Граф<ref>На самом деле, ''двойственный граф'' — '''псевдограф''', поскольку в нём могут быть петли и кратные рёбра.</ref> | + | |definition=Граф<ref>На самом деле, ''двойственный граф'' — '''псевдограф''', поскольку в нём могут быть петли и кратные рёбра.</ref> <tex>G</tex> называется '''двойственным''' к планарному графу <tex>G</tex>, если: |
| − | # Вершины | + | # Вершины <tex>G'</tex> соответствуют граням <tex>G</tex> |
| − | # Между двумя вершинами в ''G′'' есть ребро тогда и только тогда, когда соответствующие грани в | + | # Между двумя вершинами в ''G′'' есть ребро тогда и только тогда, когда соответствующие грани в <tex>G</tex> имеют общее ребро |
}} | }} | ||
[[Файл:Dual_graph.png|thumb|right|Граф (белые вершины) и двойственный ему (полосатые вершины).]] | [[Файл:Dual_graph.png|thumb|right|Граф (белые вершины) и двойственный ему (полосатые вершины).]] | ||
| Строка 12: | Строка 12: | ||
| − | Чтобы для данного плоского графа | + | Чтобы для данного плоского графа <tex>G</tex> построить двойственный <tex>G'</tex>, необходимо поместить по вершине <tex>G'</tex> в каждую грань <tex>G</tex> (включая внешнюю), а затем, если две грани в <tex>G</tex> имеют общее ребро, соединить ребром соответствующие им вершины в <tex>G'</tex> (если грани имеют несколько общих рёбер, соответствующие вершины следует соединить несколькими параллельными рёбрами). В результате всегда получится плоский псевдограф. |
Например: тетраэдр — самодвойственный граф, куб и октаэдр — двойственные, так же как додекаэдр и икосаэдр. Эти пять графов, образованные вершинами и рёбрами правильных многогранников, называют ''платоновыми''. | Например: тетраэдр — самодвойственный граф, куб и октаэдр — двойственные, так же как додекаэдр и икосаэдр. Эти пять графов, образованные вершинами и рёбрами правильных многогранников, называют ''платоновыми''. | ||
| Строка 20: | Строка 20: | ||
== Свойства == | == Свойства == | ||
[[Файл:Treenflower.png|thumb|right|Дерево и двойственный к нему «цветок».]] | [[Файл: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>, у него должен быть единственный ''двойственный граф'' | * Поскольку любой трёхсвязный планарный граф допускает только одну укладку на сфере<ref>''Харари, Ф.'' Теория графов. — М.: Книжный дом «ЛИБРОКОМ», 2009. — Теорема 11.5 — С. 130. — ISBN 978-5-397-00622-4.</ref>, у него должен быть единственный ''двойственный граф'' | ||
Версия 10:43, 19 января 2011
Эта статья находится в разработке!
Определение:
Граф[1] называется двойственным к планарному графу , если:
- Вершины соответствуют граням
- Между двумя вершинами в G′ есть ребро тогда и только тогда, когда соответствующие грани в имеют общее ребро
Чтобы для данного плоского графа построить двойственный , необходимо поместить по вершине в каждую грань (включая внешнюю), а затем, если две грани в имеют общее ребро, соединить ребром соответствующие им вершины в (если грани имеют несколько общих рёбер, соответствующие вершины следует соединить несколькими параллельными рёбрами). В результате всегда получится плоский псевдограф.
Например: тетраэдр — самодвойственный граф, куб и октаэдр — двойственные, так же как додекаэдр и икосаэдр. Эти пять графов, образованные вершинами и рёбрами правильных многогранников, называют платоновыми.
Свойства
- Если — двойственный к двусвязному графу , то — двойственный к
- У одного и того же графа может быть несколько двойственных, в зависимости от конкретной укладки (см. картинку)
- Поскольку любой трёхсвязный планарный граф допускает только одну укладку на сфере[2], у него должен быть единственный двойственный граф
- Мост переходит в петлю, а петля — в мост
- Мультиграф, двойственный к дереву, — цветок
Самодвойственные графы
Определение:
Планарный граф называется самодвойственным, если он изоморфен своему двойственному графу.
Утверждение:
и — самодвойственные графы. Среди полных графов других самодвойственных нет.
Проверить, что и полны и самодвойственны несложно. Докажем, что других нет.
Поскольку грани графа переходят в рёбра, количество рёбер и граней в исходном графе должно совпадать, т.е. .
Подставив в формулу Эйлера имеем: .
В полном графе .
Получаем квадратное уравнение: .
Его решения: и .
Таким образом, чтобы полный граф был самодвойственным, в нём должна быть ровно одна или четыре вершины.
Поскольку грани графа переходят в рёбра, количество рёбер и граней в исходном графе должно совпадать, т.е. .
Подставив в формулу Эйлера имеем: .
В полном графе .
Получаем квадратное уравнение: .
Его решения: и .
Таким образом, чтобы полный граф был самодвойственным, в нём должна быть ровно одна или четыре вершины.
Утверждение:
Все колёса самодвойственны.
Это утверждение очевидно.
Достаточно убедиться, что два варианта укладки колеса (вершина с большой степенью внутри или вершина с большой степенью снаружи) двойственны друг другу.
Достаточно убедиться, что два варианта укладки колеса (вершина с большой степенью внутри или вершина с большой степенью снаружи) двойственны друг другу.
