Изменения

{{В разработкеОпределение|neat=neat|definition=Граф<ref>На самом деле, ''двойственный граф'' — '''псевдограф''', поскольку в нём могут быть петли и кратные рёбра.</ref> <tex>G'</tex> называется '''двойственным''' (англ. ''dual graph'') к [[Укладка графа на плоскости|планарному графу]] <tex>G</tex>, если:# Вершины <tex>G'</tex> соответствуют граням <tex>G</tex>.# Между двумя вершинами в <tex>G'</tex> есть ребро тогда и только тогда, когда соответствующие грани в <tex>G</tex> имеют общее ребро.}}[[Файл:Dual_graph_2.png|180px|thumb|right|Граф (белые вершины) и двойственный ему (серые вершины).]]<div style='clear:left;'></div>

Чтобы для данного плоского графа <div style="background-color: #fcfcfc; float:left;"tex>G</tex>построить двойственный <div style="background-color: #ddd;"tex>'''Определение''G'</divtex>, необходимо поместить по вершине <div style="border:1px dashed #2f6fab; padding: 8px; font-style: italic;"tex>ГрафG'<ref/tex>На самом деле, ''двойственный граф'' — '''мультиграф''', поскольку в нём могут быть петли и кратные рёбра.каждую грань <tex>G</reftex> ''G&prime;'' называется '''двойственным''' к планарному графу ''G''(включая внешнюю), а затем, если:# Вершины ''G&prime;'' соответствуют граням ''G''# Между двумя вершинами две грани в ''<tex>G&prime;'' есть </tex> имеют общее ребро тогда и только тогда, когда соединить ребром соответствующие грани им вершины в ''<tex>G'' имеют общее ребро</divtex>(если грани имеют несколько общих рёбер, соответствующие вершины следует соединить несколькими параллельными рёбрами). В результате всегда получится плоский псевдограф. Например, существуют графы, двойственные себе: — <tex>K_1</divtex>[[Файл:Dual_graph.png|thumb|right|Граф (белые вершины) и двойственный ему (полосатые вершины).]]<div style="clear:left;"tex>K_4</divtex>. Далее мы убедимся, что среди полных графов только они обладают таким свойством.

[[Файл:Treenflowernew.png|250px|thumb|right|Дерево и двойственный к нему «цветок».‎]]* Если ''<tex>G&prime;'' </tex> — ''двойственный'' к двусвязному графу ''<tex>G''</tex>, то ''<tex>G'' </tex> — ''двойственный'' к ''<tex>G&prime;''</tex>.* У одного и того же графа может быть несколько ''двойственных'', в зависимости от конкретной укладки (см. картинку).* Поскольку любой трёхсвязный планарный граф допускает только одну укладку на сфере<ref>Харари, Ф. Теория графов. — М.: Книжный дом «ЛИБРОКОМ», 2009. — Теорема 11.5 — С. 130. — ISBN 978­-5­-397­-00622­-4</ref>, у него должен быть единственный ''двойственный граф''.* [[Мост , эквивалентные определения|Мост]] переходит в петлю, а петля — в мост. Частный случай: полный граф <tex>K_2</tex>* Мультиграф, ''двойственный '' к дереву , — цветок.  == Самодвойственные графы =={{Определение|definition=Планарный граф называется '''самодвойственным''' (англ. ''self-dual graph''), если он изоморфен своему двойственному графу.}}<div style='clear:left;'></div>  {|align="center" |-valign="top" |[[Файл:Wheel8_new2.png|500px|thumb|left|Колесо и двойственный ему граф {{---}} тоже колесо.]] |[[Файл:K4_new.png|250px|thumb|right|<tex>K_4</tex> (он же колесо).]] |}   {{Утверждение|neat=neat|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 = \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/>Таким образом, чтобы ''полный'' граф был ''самодвойственным'', в нём должна быть ровно '''одна''' или '''четыре''' вершины.}} <div style='clear: both;'><br/></div>{{Утверждение|neat=neat|statement=Все колёса самодвойственны.|proof=Это утверждение очевидно.<br/>Достаточно убедиться, что два варианта укладки колеса (вершина с большой степенью внутри или вершина с большой степенью снаружи) двойственны друг другу.}}