Двойственный граф планарного графа — различия между версиями
Kirelagin (обсуждение | вклад) |
Kirelagin (обсуждение | вклад) |
||
| Строка 4: | Строка 4: | ||
<div style="background-color: #fcfcfc; float:left;"> | <div style="background-color: #fcfcfc; float:left;"> | ||
<div style="background-color: #ddd;">'''Определение'''</div> | <div style="background-color: #ddd;">'''Определение'''</div> | ||
| − | <div style="border:1px dashed #2f6fab; padding: 8px; font-style: italic;">Граф<ref>На самом деле, ''двойственный граф'' — ''' | + | <div style="border:1px dashed #2f6fab; padding: 8px; font-style: italic;">Граф<ref>На самом деле, ''двойственный граф'' — '''псевдограф''', поскольку в нём могут быть петли и кратные рёбра.</ref> ''G′'' называется '''двойственным''' к планарному графу ''G'', если: |
# Вершины ''G′'' соответствуют граням ''G'' | # Вершины ''G′'' соответствуют граням ''G'' | ||
# Между двумя вершинами в ''G′'' есть ребро тогда и только тогда, когда соответствующие грани в ''G'' имеют общее ребро</div> | # Между двумя вершинами в ''G′'' есть ребро тогда и только тогда, когда соответствующие грани в ''G'' имеют общее ребро</div> | ||
| Строка 12: | Строка 12: | ||
| − | «…Для данного плоского графа ''G'' его ''двойственный граф G′ ''строится следующим образом: поместим в каждую область ''G'' (включая внешнюю) по одной вершине графа ''G′'' и, если две области имеют общее ребро ''x'', соединим помещенные в них вершины ребром ''x′'', пересекающим только ''x''. В результате всегда получится плоский псевдограф. Ясно, что ''G′'' имеет петлю тогда и только тогда, когда в ''G'' есть концевая вершина; ''G′'' имеет кратные рёбра тогда и только тогда, когда две области графа ''G'' содержат по крайней мере два общих ребра. Таким образом, двусвязный плоский граф имеет всегда в качестве двойственного или граф или мультиграф, в то время как двойственный граф трёхсвязного плоского графа всегда представляет собой граф. Другими примерами двойственных графов являются платоновы графы: тетраэдр — самодвойственный граф, куб и октаэдр — двойственные, так же как додекаэдр и икосаэдр…»<ref>''Харари, Ф.'' Теория графов. | + | «…Для данного плоского графа ''G'' его ''двойственный граф G′ ''строится следующим образом: поместим в каждую область ''G'' (включая внешнюю) по одной вершине графа ''G′'' и, если две области имеют общее ребро ''x'', соединим помещенные в них вершины ребром ''x′'', пересекающим только ''x''. В результате всегда получится плоский псевдограф. Ясно, что ''G′'' имеет петлю тогда и только тогда, когда в ''G'' есть концевая вершина; ''G′'' имеет кратные рёбра тогда и только тогда, когда две области графа ''G'' содержат по крайней мере два общих ребра. Таким образом, двусвязный плоский граф имеет всегда в качестве двойственного или граф или мультиграф, в то время как двойственный граф трёхсвязного плоского графа всегда представляет собой граф. Другими примерами двойственных графов являются платоновы графы: тетраэдр — самодвойственный граф, куб и октаэдр — двойственные, так же как додекаэдр и икосаэдр…»<ref>''Харари, Ф.'' Теория графов. — М.: Книжный дом «ЛИБРОКОМ», 2009. — С. 138. — ISBN 978-5-397-00622-4.</ref>. |
[[Файл:Noniso_dual_graphs.png|thumb|left|В верхнем двойственном графе есть вершина степени 6, а в нижнем — нет. Следовательно, они не изоморфны.]] | [[Файл:Noniso_dual_graphs.png|thumb|left|В верхнем двойственном графе есть вершина степени 6, а в нижнем — нет. Следовательно, они не изоморфны.]] | ||
| Строка 18: | Строка 18: | ||
[[Файл:Treenflower.png|thumb|right|Дерево и двойственный к нему «цветок».]] | [[Файл:Treenflower.png|thumb|right|Дерево и двойственный к нему «цветок».]] | ||
* Если ''G′'' — ''двойственный'' к двусвязному графу ''G'', то ''G'' — ''двойственный'' к ''G′'' | * Если ''G′'' — ''двойственный'' к двусвязному графу ''G'', то ''G'' — ''двойственный'' к ''G′'' | ||
| − | * У одного и того же графа может быть несколько двойственных, в зависимости от конкретной укладки (см. картинку) | + | * У одного и того же графа может быть несколько ''двойственных'', в зависимости от конкретной укладки (см. картинку) |
| + | * Поскольку любой трёхсвязный планарный граф допускает только одну укладку на сфере<ref>''Харари, Ф.'' Теория графов. — М.: Книжный дом «ЛИБРОКОМ», 2009. — Теорема 11.5 — С. 130. — ISBN 978-5-397-00622-4.</ref>, у него должен быть единственный ''двойственный граф'' | ||
* Мост переходит в петлю, а петля — в мост | * Мост переходит в петлю, а петля — в мост | ||
| − | * Мультиграф, двойственный к дереву — цветок | + | * Мультиграф, ''двойственный'' к дереву, — цветок |
<div style="clear:both;"></div> | <div style="clear:both;"></div> | ||
Версия 03:26, 9 октября 2010
Эта статья находится в разработке!
Определение
Граф[1] G′ называется двойственным к планарному графу G, если:
- Вершины 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.
