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

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 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>На самом деле, ''двойственный граф'' — '''мультиграф''', поскольку в нём могут быть петли и кратные рёбра</ref> ''G&prime;'' называется '''двойственным''' к планарному графу ''G'', если:
+
<div style="border:1px dashed #2f6fab; padding: 8px; font-style: italic;">Граф<ref>На самом деле, ''двойственный граф'' — '''мультиграф''', поскольку в нём могут быть петли и кратные рёбра.</ref> ''G&prime;'' называется '''двойственным''' к планарному графу ''G'', если:
 
# Вершины ''G&prime;'' соответствуют граням ''G''
 
# Вершины ''G&prime;'' соответствуют граням ''G''
 
# Между двумя вершинами в ''G&prime;'' есть ребро тогда и только тогда, когда соответствующие грани в ''G'' имеют общее ребро</div>
 
# Между двумя вершинами в ''G&prime;'' есть ребро тогда и только тогда, когда соответствующие грани в ''G'' имеют общее ребро</div>
Строка 12: Строка 12:
  
  
«…Для данного плоского графа ''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>.
+
«…Для данного плоского графа ''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>.
  
 +
[[Файл:Noniso_dual_graphs.png|thumb|left|В верхнем двойственном графе есть вершина степени 6, а в нижнем — нет. Следовательно, они не изоморфны.]]
 
== Свойства ==
 
== Свойства ==
[[Файл:Noniso_dual_graphs.png|thumb|left|В верхнем двойственном графе есть вершина степени 6, а в нижнем — нет. Следовательно, они не изоморфны.]]
+
[[Файл:Treenflower.png|thumb|right|Дерево и двойственный к нему «цветок».]]
 
* Если ''G&prime;'' — ''двойственный'' к двусвязному графу ''G'', то ''G'' — ''двойственный'' к ''G&prime;''
 
* Если ''G&prime;'' — ''двойственный'' к двусвязному графу ''G'', то ''G'' — ''двойственный'' к ''G&prime;''
 
* У одного и того же графа может быть несколько двойственных, в зависимости от конкретной укладки (см. картинку)
 
* У одного и того же графа может быть несколько двойственных, в зависимости от конкретной укладки (см. картинку)
Строка 21: Строка 22:
 
* Мультиграф, двойственный к дереву — цветок
 
* Мультиграф, двойственный к дереву — цветок
  
 +
<div style="clear:both;"></div>
 
== Примечания ==
 
== Примечания ==
 
<references />
 
<references />

Версия 02:13, 9 октября 2010

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


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


«…Для данного плоского графа G его двойственный граф G′ строится следующим образом: поместим в каждую область G (включая внешнюю) по одной вершине графа G′ и, если две области имеют общее ребро x, соединим помещенные в них вершины ребром x′, пересекающим только x. В результате всегда получится плоский псевдограф. Ясно, что G′ имеет петлю тогда и только тогда, когда в G есть концевая вершина; G′ имеет кратные рёбра тогда и только тогда, когда две области графа G содержат по крайней мере два общих ребра. Таким образом, двусвязный плоский граф имеет всегда в качестве двойственного или граф или мультиграф, в то время как двойственный граф трёхсвязного плоского графа всегда представляет собой граф. Другими примерами двойственных графов являются платоновы графы: тетраэдр — самодвойственный граф, куб и октаэдр — двойственные, так же как додекаэдр и икосаэдр…»[2].

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

Свойства

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

Примечания

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