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

Материал из Викиконспекты
Перейти к: навигация, поиск
(фикс)
Строка 4: Строка 4:
 
{{Определение
 
{{Определение
 
|neat=neat
 
|neat=neat
|definition=Граф<ref>На самом деле, ''двойственный граф'' — '''псевдограф''', поскольку в нём могут быть петли и кратные рёбра.</ref> ''G&prime;'' называется '''двойственным''' к планарному графу ''G'', если:
+
|definition=Граф<ref>На самом деле, ''двойственный граф'' — '''псевдограф''', поскольку в нём могут быть петли и кратные рёбра.</ref> <tex>G</tex> называется '''двойственным''' к планарному графу <tex>G</tex>, если:
# Вершины ''G&prime;'' соответствуют граням ''G''
+
# Вершины <tex>G'</tex> соответствуют граням <tex>G</tex>
# Между двумя вершинами в ''G&prime;'' есть ребро тогда и только тогда, когда соответствующие грани в ''G'' имеют общее ребро
+
# Между двумя вершинами в ''G&prime;'' есть ребро тогда и только тогда, когда соответствующие грани в <tex>G</tex> имеют общее ребро
 
}}
 
}}
 
[[Файл:Dual_graph.png|thumb|right|Граф (белые вершины) и двойственный ему (полосатые вершины).]]
 
[[Файл:Dual_graph.png|thumb|right|Граф (белые вершины) и двойственный ему (полосатые вершины).]]
Строка 12: Строка 12:
  
  
Чтобы для данного плоского графа ''G'' построить двойственный ''G&prime;'', необходимо поместить по вершине ''G&prime;'' в каждую грань ''G'' (включая внешнюю), а затем, если две грани в ''G'' имеют общее ребро, соединить ребром соответствующие им вершины в ''G&prime;'' (если грани имеют несколько общих рёбер, соответствующие вершины следует соединить несколькими параллельными рёбрами). В результате всегда получится плоский псевдограф.
+
Чтобы для данного плоского графа <tex>G</tex> построить двойственный <tex>G'</tex>, необходимо поместить по вершине <tex>G'</tex> в каждую грань <tex>G</tex> (включая внешнюю), а затем, если две грани в <tex>G</tex> имеют общее ребро, соединить ребром соответствующие им вершины в <tex>G'</tex> (если грани имеют несколько общих рёбер, соответствующие вершины следует соединить несколькими параллельными рёбрами). В результате всегда получится плоский псевдограф.
  
 
Например: тетраэдр — самодвойственный граф, куб и октаэдр — двойственные, так же как додекаэдр и икосаэдр. Эти пять графов, образованные вершинами и рёбрами правильных многогранников, называют ''платоновыми''.
 
Например: тетраэдр — самодвойственный граф, куб и октаэдр — двойственные, так же как додекаэдр и икосаэдр. Эти пять графов, образованные вершинами и рёбрами правильных многогранников, называют ''платоновыми''.
Строка 20: Строка 20:
 
== Свойства ==
 
== Свойства ==
 
[[Файл:Treenflower.png|thumb|right|Дерево и двойственный к нему «цветок».‎]]
 
[[Файл:Treenflower.png|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>, у него должен быть единственный ''двойственный граф''

Версия 10:43, 19 января 2011

Эта статья находится в разработке!


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


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

Например: тетраэдр — самодвойственный граф, куб и октаэдр — двойственные, так же как додекаэдр и икосаэдр. Эти пять графов, образованные вершинами и рёбрами правильных многогранников, называют платоновыми.


В верхнем двойственном графе есть вершина степени 6, а в нижнем — нет. Следовательно, они не изоморфны.

Свойства

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


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

Определение:
Планарный граф называется самодвойственным, если он изоморфен своему двойственному графу.
Колесо и колесо.
[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 = \frac{E}{2} + 1[/math].
В полном графе [math]E = \frac{V \dot (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.