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