Двойственный граф планарного графа — различия между версиями
Kirelagin (обсуждение | вклад) |
Kirelagin (обсуждение | вклад) м (Переделал с помощью исправленного шаблона определения) |
||
| Строка 2: | Строка 2: | ||
| − | + | {{Определение | |
| − | + | |neat=neat | |
| − | + | |definition=Граф<ref>На самом деле, ''двойственный граф'' — '''псевдограф''', поскольку в нём могут быть петли и кратные рёбра.</ref> ''G′'' называется '''двойственным''' к планарному графу ''G'', если: | |
# Вершины ''G′'' соответствуют граням ''G'' | # Вершины ''G′'' соответствуют граням ''G'' | ||
| − | # Между двумя вершинами в ''G′'' есть ребро тогда и только тогда, когда соответствующие грани в ''G'' имеют общее ребро | + | # Между двумя вершинами в ''G′'' есть ребро тогда и только тогда, когда соответствующие грани в ''G'' имеют общее ребро |
| − | + | }} | |
[[Файл:Dual_graph.png|thumb|right|Граф (белые вершины) и двойственный ему (полосатые вершины).]] | [[Файл:Dual_graph.png|thumb|right|Граф (белые вершины) и двойственный ему (полосатые вершины).]] | ||
| − | <div style= | + | <div style='clear:left;'></div> |
Версия 09:23, 17 октября 2010
- Вершины G′ соответствуют граням G
- Между двумя вершинами в G′ есть ребро тогда и только тогда, когда соответствующие грани в G имеют общее ребро
«…Для данного плоского графа G его двойственный граф G′ строится следующим образом: поместим в каждую область G (включая внешнюю) по одной вершине графа G′ и, если две области имеют общее ребро x, соединим помещенные в них вершины ребром x′, пересекающим только x. В результате всегда получится плоский псевдограф. Ясно, что G′ имеет петлю тогда и только тогда, когда в G есть концевая вершина; G′ имеет кратные рёбра тогда и только тогда, когда две области графа G содержат по крайней мере два общих ребра. Таким образом, двусвязный плоский граф имеет всегда в качестве двойственного или граф или мультиграф, в то время как двойственный граф трёхсвязного плоского графа всегда представляет собой граф. Другими примерами двойственных графов являются платоновы графы: тетраэдр — самодвойственный граф, куб и октаэдр — двойственные, так же как додекаэдр и икосаэдр…»[2].
Свойства
- Если G′ — двойственный к двусвязному графу G, то G — двойственный к G′
- У одного и того же графа может быть несколько двойственных, в зависимости от конкретной укладки (см. картинку)
- Поскольку любой трёхсвязный планарный граф допускает только одну укладку на сфере[3], у него должен быть единственный двойственный граф
- Мост переходит в петлю, а петля — в мост
- Мультиграф, двойственный к дереву, — цветок
Примечания
- ↑ На самом деле, двойственный граф — псевдограф, поскольку в нём могут быть петли и кратные рёбра.
- ↑ Харари, Ф. Теория графов. — М.: Книжный дом «ЛИБРОКОМ», 2009. — С. 138. — ISBN 978-5-397-00622-4.
- ↑ Харари, Ф. Теория графов. — М.: Книжный дом «ЛИБРОКОМ», 2009. — Теорема 11.5 — С. 130. — ISBN 978-5-397-00622-4.
