Двойственный граф планарного графа — различия между версиями
Slavian (обсуждение | вклад) |
Lehanyich (обсуждение | вклад) |
||
| Строка 1: | Строка 1: | ||
{{Определение | {{Определение | ||
|neat=neat | |neat=neat | ||
| − | |definition=Граф<ref>На самом деле, ''двойственный граф'' — '''псевдограф''', поскольку в нём могут быть петли и кратные рёбра.</ref> <tex>G'</tex> называется '''двойственным'''(англ. ''dual graph'') к планарному графу <tex>G</tex>, если: | + | |definition=Граф<ref>На самом деле, ''двойственный граф'' — '''псевдограф''', поскольку в нём могут быть петли и кратные рёбра.</ref> <tex>G'</tex> называется '''двойственным''' (англ. ''dual graph'') к [[Укладка графа на плоскости|планарному графу]] <tex>G</tex>, если: |
# Вершины <tex>G'</tex> соответствуют граням <tex>G</tex> | # Вершины <tex>G'</tex> соответствуют граням <tex>G</tex> | ||
# Между двумя вершинами в <tex>G'</tex> есть ребро тогда и только тогда, когда соответствующие грани в <tex>G</tex> имеют общее ребро | # Между двумя вершинами в <tex>G'</tex> есть ребро тогда и только тогда, когда соответствующие грани в <tex>G</tex> имеют общее ребро | ||
| Строка 19: | Строка 19: | ||
* Если <tex>G'</tex> — ''двойственный'' к двусвязному графу <tex>G</tex>, то <tex>G</tex> — ''двойственный'' к <tex>G'</tex> | * Если <tex>G'</tex> — ''двойственный'' к двусвязному графу <tex>G</tex>, то <tex>G</tex> — ''двойственный'' к <tex>G'</tex> | ||
* У одного и того же графа может быть несколько ''двойственных'', в зависимости от конкретной укладки (см. картинку) | * У одного и того же графа может быть несколько ''двойственных'', в зависимости от конкретной укладки (см. картинку) | ||
| − | * Поскольку любой трёхсвязный планарный граф допускает только одну укладку на сфере<ref>Харари, Ф. Теория графов. — М.: Книжный дом «ЛИБРОКОМ», 2009. — Теорема 11.5 — С. 130. — ISBN 978-5-397-00622-4 | + | * Поскольку любой трёхсвязный планарный граф допускает только одну укладку на сфере<ref>Харари, Ф. Теория графов. — М.: Книжный дом «ЛИБРОКОМ», 2009. — Теорема 11.5 — С. 130. — ISBN 978-5-397-00622-4</ref>, у него должен быть единственный ''двойственный граф'' |
| − | * Мост переходит в петлю, а петля — в мост | + | * [[Мост, эквивалентные определения|Мост]] переходит в петлю, а петля — в мост |
* Мультиграф, ''двойственный'' к дереву, — цветок | * Мультиграф, ''двойственный'' к дереву, — цветок | ||
| Строка 26: | Строка 26: | ||
== Самодвойственные графы == | == Самодвойственные графы == | ||
{{Определение | {{Определение | ||
| − | |||
|definition=Планарный граф называется '''самодвойственным''', если он изоморфен своему двойственному графу. | |definition=Планарный граф называется '''самодвойственным''', если он изоморфен своему двойственному графу. | ||
}} | }} | ||
| Строка 43: | Строка 42: | ||
|neat=neat | |neat=neat | ||
|statement=<tex>K_1</tex> и <tex>K_4</tex> — самодвойственные графы. Среди полных графов других самодвойственных нет. | |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 = \ | + | |proof=Проверить, что <tex>K_1</tex> и <tex>K_4</tex> полны и самодвойственны несложно. Докажем, что других нет.<br/>Поскольку грани графа переходят в вершины, количество вершин и граней в исходном графе должно совпадать, т.е. <tex>V = F</tex>.<br/>Подставив в [[Формула Эйлера|формулу Эйлера]] имеем: <tex>2V = E + 2 \Leftrightarrow V = \dfrac{E}{2} + 1</tex>.<br/>В полном графе <tex>E = \dfrac{V \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/>Таким образом, чтобы ''полный'' граф был ''самодвойственным'', в нём должна быть ровно '''одна''' или '''четыре''' вершины. |
}} | }} | ||
| Строка 54: | Строка 53: | ||
<div style="clear:both;"></div> | <div style="clear:both;"></div> | ||
| + | |||
| + | == См. также == | ||
| + | *[[Формула Эйлера]] | ||
| + | *[[Укладка графа на плоскости]] | ||
| + | *[[Гамма-алгоритм]] | ||
== Примечания == | == Примечания == | ||
<references /> | <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 Википедия — Планарный граф] | ||
[[Категория: Алгоритмы и структуры данных]] | [[Категория: Алгоритмы и структуры данных]] | ||
[[Категория: Укладки графов]] | [[Категория: Укладки графов]] | ||
Версия 21:51, 21 ноября 2015
Определение:
Граф[1] называется двойственным (англ. dual graph) к планарному графу , если:
- Вершины соответствуют граням
- Между двумя вершинами в есть ребро тогда и только тогда, когда соответствующие грани в имеют общее ребро
Чтобы для данного плоского графа построить двойственный , необходимо поместить по вершине в каждую грань (включая внешнюю), а затем, если две грани в имеют общее ребро, соединить ребром соответствующие им вершины в (если грани имеют несколько общих рёбер, соответствующие вершины следует соединить несколькими параллельными рёбрами). В результате всегда получится плоский псевдограф.
Например: тетраэдр — самодвойственный граф, куб и октаэдр — двойственные, так же как додекаэдр и икосаэдр. Эти пять графов, образованные вершинами и рёбрами правильных многогранников, называют платоновыми.
Свойства
- Если — двойственный к двусвязному графу , то — двойственный к
- У одного и того же графа может быть несколько двойственных, в зависимости от конкретной укладки (см. картинку)
- Поскольку любой трёхсвязный планарный граф допускает только одну укладку на сфере[2], у него должен быть единственный двойственный граф
- Мост переходит в петлю, а петля — в мост
- Мультиграф, двойственный к дереву, — цветок
Самодвойственные графы
| Определение: |
| Планарный граф называется самодвойственным, если он изоморфен своему двойственному графу. |
Утверждение:
и — самодвойственные графы. Среди полных графов других самодвойственных нет.
Проверить, что и полны и самодвойственны несложно. Докажем, что других нет.
Поскольку грани графа переходят в вершины, количество вершин и граней в исходном графе должно совпадать, т.е. .
Подставив в формулу Эйлера имеем: .
В полном графе .
Получаем квадратное уравнение: .
Его решения: и .
Таким образом, чтобы полный граф был самодвойственным, в нём должна быть ровно одна или четыре вершины.
Поскольку грани графа переходят в вершины, количество вершин и граней в исходном графе должно совпадать, т.е. .
Подставив в формулу Эйлера имеем: .
В полном графе .
Получаем квадратное уравнение: .
Его решения: и .
Таким образом, чтобы полный граф был самодвойственным, в нём должна быть ровно одна или четыре вершины.
Утверждение:
Все колёса самодвойственны.
Это утверждение очевидно.
Достаточно убедиться, что два варианта укладки колеса (вершина с большой степенью внутри или вершина с большой степенью снаружи) двойственны друг другу.
Достаточно убедиться, что два варианта укладки колеса (вершина с большой степенью внутри или вершина с большой степенью снаружи) двойственны друг другу.
