Двойственный граф планарного графа — различия между версиями
Kirelagin (обсуждение | вклад) |
Kirelagin (обсуждение | вклад) |
||
| Строка 31: | Строка 31: | ||
}} | }} | ||
<div style='clear:left;'></div> | <div style='clear:left;'></div> | ||
| − | |||
[[Файл:Wheel_8.png|thumb|left|Колесо и колесо.]] | [[Файл:Wheel_8.png|thumb|left|Колесо и колесо.]] | ||
| + | [[Файл:K4.png|thumb|right|<tex>K_4</tex> (он же кольцо).]] | ||
| − | + | <div style='float:left;'> | |
| + | {{Утверждение | ||
| + | |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> полны и самодвойственны несложно. Докажем, что других нет. | + | |proof=Проверить, что <tex>K_1</tex> и <tex>K_4</tex> полны и самодвойственны несложно. Докажем, что других нет.<br/>Поскольку грани графа переходят в рёбра, количество рёбер и граней в исходном графе должно совпадать, т.е. <tex>V = F</tex>.<br/>Подставив в [[Формула Эйлера|формулу Эйлера]] имеем: <tex>2V = E + 2 \Leftrightarrow V = \frac{E}{2} + 1</tex>.<br/>В полном графе <tex>E = \frac{V \dot (V - 1)}{2}</tex>.<br/>Получаем квадратное уравнение: <tex>V^2 - 5V + 4 = 0</tex>.<br/>Его решения: <tex>V_1 = 1</tex> и <tex>V_2 = 4</tex>.<br/>Таким образом, чтобы ''полный'' граф был ''самодвойственным'', в нём должна быть ровно '''одна''' или '''четыре''' вершины. |
| − | Поскольку грани графа переходят в рёбра, количество рёбер и граней в исходном графе должно совпадать, т.е. <tex>V = F</tex>. | + | }} |
| − | + | <div style='clear: both;'><br/></div> | |
| − | + | {{Утверждение | |
| − | + | |neat=neat | |
| − | |||
| − | |||
| − | |||
|statement=Все колёса самодвойственны. | |statement=Все колёса самодвойственны. | ||
}} | }} | ||
| + | </div> | ||
<div style="clear:both;"></div> | <div style="clear:both;"></div> | ||
Версия 07:58, 18 октября 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.
