Изменения

{{В разработкеОпределение|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>  Чтобы для данного плоского графа <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>. Далее мы убедимся, что среди полных графов только они обладают таким свойством.   == Свойства ==[[Файл:Treenflower new.png|250px|thumb|right|Дерево и двойственный к нему «цветок».‎]]* Если <tex>G'</tex> — ''двойственный'' к двусвязному графу <tex>G</tex>, то <tex>G</tex> — ''двойственный'' к <tex>G'</tex>.* У одного и того же графа может быть несколько ''двойственных'', в зависимости от конкретной укладки (см. картинку).* Поскольку любой трёхсвязный планарный граф допускает только одну укладку на сфере<ref>Харари, Ф. Теория графов. — М.: Книжный дом «ЛИБРОКОМ», 2009. — Теорема 11.5 — С. 130. — ISBN 978­-5­-397­-00622­-4</ref>, у него должен быть единственный ''двойственный граф''.* [[Мост, эквивалентные определения|Мост]] переходит в петлю, а петля — в мост. Частный случай: полный граф <tex>K_2</tex>* Мультиграф, ''двойственный'' к дереву, — цветок.

|neat=neat|definition=Граф<ref>На самом деле, ''двойственный Планарный графназывается '' — ''самодвойственным'псевдограф''', поскольку в нём могут быть петли и кратные рёбра(англ.</ref> ''G&prime;'' называется '''двойственным''' к планарному графу ''Gself-dual graph''), если:# Вершины ''G&prime;'' соответствуют граням ''G''# Между двумя вершинами в ''G&prime;'' есть ребро тогда и только тогда, когда соответствующие грани в ''G'' имеют общее реброон изоморфен своему двойственному графу.

«…Для данного плоского графа ''G'' его ''двойственный граф G&prime; ''строится следующим образом{|align="center" |-valign="top" |[[Файл: поместим в каждую область ''G'' (включая внешнюю) по одной вершине графа ''G&prime;'' и, если две области имеют общее ребро ''x'', соединим помещенные в них вершины ребром ''x&prime;'', пересекающим только ''x''. В результате всегда получится плоский псевдографWheel8_new2. Ясно, что ''G&prime;'' имеет петлю тогда и только тогда, когда в ''G'' есть концевая вершина; ''G&prime;'' имеет кратные рёбра тогда png|500px|thumb|left|Колесо и только тогда, когда две области графа ''G'' содержат по крайней мере два общих ребра. Таким образом, двусвязный плоский граф имеет всегда в качестве двойственного или граф или мультиграф, в то время как двойственный ему граф трёхсвязного плоского графа всегда представляет собой граф{{---}} тоже колесо. Другими примерами двойственных графов являются платоновы графы]] |[[Файл: тетраэдр — самодвойственный граф, куб и октаэдр — двойственные, так же как додекаэдр и икосаэдр…»K4_new.png|250px|thumb|right|<reftex>''Харари, Ф.'' Теория графов. — М.: Книжный дом «ЛИБРОКОМ», 2009. — С. 138. — ISBN 978­-5­-397­-00622­-4.K_4</reftex>(он же колесо).]] |}

[[Файл:Noniso_dual_graphs.png {{Утверждение|thumbneat=neat|leftstatement=<tex>K_1</tex> и <tex>K_4</tex> — самодвойственные графы. Среди полных графов других самодвойственных нет.|В верхнем двойственном графе есть вершина степени 6proof=Проверить, что <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/>Его решения:Treenflower.png|thumb|right|Дерево <tex>V_1 = 1</tex> и двойственный к нему «цветок»<tex>V_2 = 4</tex>.‎]]* Если ''G&prime;<br/>Таким образом, чтобы '' — полный''двойственныйграф был '' к двусвязному графу ''Gсамодвойственным'', то в нём должна быть ровно ''G'одна' — ''двойственныйили '' к 'четыре'G&prime;''вершины.}} * У одного и того же графа может быть несколько <div style='clear: both;'двойственных'', в зависимости от конкретной укладки (см. картинку)* Поскольку любой трёхсвязный планарный граф допускает только одну укладку на сфере><br/><ref/div>''Харари, Ф{{Утверждение|neat=neat|statement=Все колёса самодвойственны.'' Теория графов. — М.: Книжный дом «ЛИБРОКОМ», 2009. — Теорема 11.5 — С. 130. — ISBN 978­-5­-397­-00622­-4|proof=Это утверждение очевидно.<br/ref>Достаточно убедиться, у него должен быть единственный ''двойственный граф''* Мост переходит в петлю, а петля — в мостчто два варианта укладки колеса (вершина с большой степенью внутри или вершина с большой степенью снаружи) двойственны друг другу.* Мультиграф, ''двойственный'' к дереву, — цветок}}