Двойственный граф планарного графа — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
м (rollbackEdits.php mass rollback)
 
(не показано 37 промежуточных версий 7 участников)
Строка 1: Строка 1:
−
{{В разработке}}
 
−
 
−
 
 
{{Определение
 
{{Определение
 
|neat=neat
 
|neat=neat
−
|definition=Граф<ref>На самом деле, ''двойственный граф'' — '''псевдограф''', поскольку в нём могут быть петли и кратные рёбра.</ref> ''G&prime;'' называется '''двойственным''' к планарному графу ''G'', если:
+
|definition=Граф<ref>На самом деле, ''двойственный граф'' — '''псевдограф''', поскольку в нём могут быть петли и кратные рёбра.</ref> <tex>G'</tex> называется '''двойственным''' (англ. ''dual graph'') к [[Укладка графа на плоскости|планарному графу]] <tex>G</tex>, если:
−
# Вершины ''G&prime;'' соответствуют граням ''G''
+
# Вершины <tex>G'</tex> соответствуют граням <tex>G</tex>.
−
# Между двумя вершинами в ''G&prime;'' есть ребро тогда и только тогда, когда соответствующие грани в ''G'' имеют общее ребро
+
# Между двумя вершинами в <tex>G'</tex> есть ребро тогда и только тогда, когда соответствующие грани в <tex>G</tex> имеют общее ребро.
 
}}
 
}}
−
[[Файл:Dual_graph.png|thumb|right|Граф (белые вершины) и двойственный ему (полосатые вершины).]]
+
[[Файл:Dual_graph_2.png|180px|thumb|right|Граф (белые вершины) и двойственный ему (серые вершины).]]
 
<div style='clear:left;'></div>
 
<div style='clear:left;'></div>
  
  
−
«…Для данного плоского графа ''G'' его ''двойственный граф G&prime; ''строится следующим образом: поместим в каждую область ''G'' (включая внешнюю) по одной вершине графа ''G&prime;'' и, если две области имеют общее ребро ''x'', соединим помещенные в них вершины ребром ''x&prime;'', пересекающим только ''x''. В результате всегда получится плоский псевдограф. Ясно, что ''G&prime;'' имеет петлю тогда и только тогда, когда в ''G'' есть концевая вершина; ''G&prime;'' имеет кратные рёбра тогда и только тогда, когда две области графа ''G'' содержат по крайней мере два общих ребра. Таким образом, двусвязный плоский граф имеет всегда в качестве двойственного или граф или мультиграф, в то время как двойственный граф трёхсвязного плоского графа всегда представляет собой граф. Другими примерами двойственных графов являются платоновы графы: тетраэдр — самодвойственный граф, куб и октаэдр — двойственные, так же как додекаэдр и икосаэдр…»<ref>''Харари, Ф.'' Теория графов. — М.: Книжный дом «ЛИБРОКОМ», 2009. — С. 138. — ISBN 978­-5­-397­-00622­-4.</ref>.
+
Чтобы для данного плоского графа <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>. Далее мы убедимся, что среди полных графов только они обладают таким свойством.
 +
 
  
  
−
[[Файл:Noniso_dual_graphs.png|thumb|left|В верхнем двойственном графе есть вершина степени 6, а в нижнем — нет. Следовательно, они не изоморфны.]]
 
 
== Свойства ==
 
== Свойства ==
−
[[Файл:Treenflower.png|thumb|right|Дерево и двойственный к нему «цветок».‎]]
+
[[Файл:Treenflower new.png|250px|thumb|right|Дерево и двойственный к нему «цветок».‎]]
−
* Если ''G&prime;'' — ''двойственный'' к двусвязному графу ''G'', то ''G'' — ''двойственный'' к ''G&prime;''
+
* Если <tex>G'</tex> — ''двойственный'' к двусвязному графу <tex>G</tex>, то <tex>G</tex> — ''двойственный'' к <tex>G'</tex>.
−
* У одного и того же графа может быть несколько ''двойственных'', в зависимости от конкретной укладки (см. картинку)
+
* У одного и того же графа может быть несколько ''двойственных'', в зависимости от конкретной укладки (см. картинку).
−
* Поскольку любой трёхсвязный планарный граф допускает только одну укладку на сфере<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>
−
* Мультиграф, ''двойственный'' к дереву, — цветок
+
* Мультиграф, ''двойственный'' к дереву, — цветок.
  
  
 
== Самодвойственные графы ==
 
== Самодвойственные графы ==
 
{{Определение
 
{{Определение
−
|neat=neat
+
|definition=Планарный граф называется '''самодвойственным''' (англ. ''self-dual graph''), если он изоморфен своему двойственному графу.
−
|definition=Планарный граф называется '''самодвойственным''', если он изоморфен своему двойственному графу.
 
 
}}
 
}}
 
<div style='clear:left;'></div>
 
<div style='clear:left;'></div>
−
[[Файл:Wheel_8.png|thumb|left|Колесо и колесо.]]
 
−
[[Файл:K4.png|thumb|right|<tex>K_4</tex> (он же кольцо).]]
 
  
  
−
<div style='float:left;'>
+
{|align="center"
 +
|-valign="top"
 +
|[[Файл:Wheel8_new2.png|500px|thumb|left|Колесо и двойственный ему граф {{---}} тоже колесо.]]
 +
|[[Файл:K4_new.png|250px|thumb|right|<tex>K_4</tex> (он же колесо).]]
 +
|}
 +
 
 +
 
 +
 
 
{{Утверждение
 
{{Утверждение
 
|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 = \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/>Таким образом, чтобы ''полный'' граф был ''самодвойственным'', в нём должна быть ровно '''одна''' или '''четыре''' вершины.
+
|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/>Таким образом, чтобы ''полный'' граф был ''самодвойственным'', в нём должна быть ровно '''одна''' или '''четыре''' вершины.
 
}}
 
}}
  
Строка 46: Строка 49:
 
|neat=neat
 
|neat=neat
 
|statement=Все колёса самодвойственны.
 
|statement=Все колёса самодвойственны.
 +
|proof=Это утверждение очевидно.<br/>Достаточно убедиться, что два варианта укладки колеса (вершина с большой степенью внутри или вершина с большой степенью снаружи) двойственны друг другу.
 
}}
 
}}
−
</div>
 
  
 
<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 Википедия — Планарный граф]
  
 
[[Категория: Алгоритмы и структуры данных]]
 
[[Категория: Алгоритмы и структуры данных]]
 
[[Категория: Укладки графов]]
 
[[Категория: Укладки графов]]

Текущая версия на 19:25, 4 сентября 2022

Определение:
Граф[1] [math]G'[/math] называется двойственным (англ. dual graph) к планарному графу [math]G[/math], если:
  1. Вершины [math]G'[/math] соответствуют граням [math]G[/math].
  2. Между двумя вершинами в [math]G'[/math] есть ребро тогда и только тогда, когда соответствующие грани в [math]G[/math] имеют общее ребро.
Граф (белые вершины) и двойственный ему (серые вершины).


Чтобы для данного плоского графа [math]G[/math] построить двойственный [math]G'[/math], необходимо поместить по вершине [math]G'[/math] в каждую грань [math]G[/math] (включая внешнюю), а затем, если две грани в [math]G[/math] имеют общее ребро, соединить ребром соответствующие им вершины в [math]G'[/math] (если грани имеют несколько общих рёбер, соответствующие вершины следует соединить несколькими параллельными рёбрами). В результате всегда получится плоский псевдограф.

Например, существуют графы, двойственные себе: — [math]K_1[/math] и [math]K_4[/math]. Далее мы убедимся, что среди полных графов только они обладают таким свойством.


Свойства

Дерево и двойственный к нему «цветок».‎
  • Если [math]G'[/math] — двойственный к двусвязному графу [math]G[/math], то [math]G[/math] — двойственный к [math]G'[/math].
  • У одного и того же графа может быть несколько двойственных, в зависимости от конкретной укладки (см. картинку).
  • Поскольку любой трёхсвязный планарный граф допускает только одну укладку на сфере[2], у него должен быть единственный двойственный граф.
  • Мост переходит в петлю, а петля — в мост. Частный случай: полный граф [math]K_2[/math]
  • Мультиграф, двойственный к дереву, — цветок.


Самодвойственные графы

Определение:
Планарный граф называется самодвойственным (англ. self-dual graph), если он изоморфен своему двойственному графу.


Колесо и двойственный ему граф — тоже колесо.
[math]K_4[/math] (он же колесо).


Утверждение:
[math]K_1[/math] и [math]K_4[/math] — самодвойственные графы. Среди полных графов других самодвойственных нет.
[math]\triangleright[/math]
Проверить, что [math]K_1[/math] и [math]K_4[/math] полны и самодвойственны несложно. Докажем, что других нет.
Поскольку грани графа переходят в вершины, количество вершин и граней в исходном графе должно совпадать, т.е. [math]V = F[/math].
Подставив в формулу Эйлера имеем: [math]2V = E + 2 \Leftrightarrow V = \dfrac{E}{2} + 1[/math].
В полном графе [math]E = \dfrac{V \cdot (V - 1)}{2}[/math].
Получаем квадратное уравнение: [math]V^2 - 5V + 4 = 0[/math].
Его решения: [math]V_1 = 1[/math] и [math]V_2 = 4[/math].
Таким образом, чтобы полный граф был самодвойственным, в нём должна быть ровно одна или четыре вершины.
[math]\triangleleft[/math]

Утверждение:
Все колёса самодвойственны.
[math]\triangleright[/math]
Это утверждение очевидно.
Достаточно убедиться, что два варианта укладки колеса (вершина с большой степенью внутри или вершина с большой степенью снаружи) двойственны друг другу.
[math]\triangleleft[/math]

См. также

Примечания

  1. ↑ На самом деле, двойственный граф — псевдограф, поскольку в нём могут быть петли и кратные рёбра.
  2. ↑ Харари, Ф. Теория графов. — М.: Книжный дом «ЛИБРОКОМ», 2009. — Теорема 11.5 — С. 130. — ISBN 978­-5­-397­-00622­-4

Источники информации

Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Двойственный_граф_планарного_графа&oldid=85119»