Изменения

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

[[Файл:Dual_graphDual_graph_2.png|180px|thumb|right|Граф (белые вершины) и двойственный ему (полосатые серые вершины).]]

«…Для Чтобы для данного плоского графа ''<tex>G'' его ''</tex> построить двойственный граф <tex>G&prime; '</tex>, необходимо поместить по вершине <tex>G'строится следующим образом: поместим </tex> в каждую область ''грань <tex>G'' </tex> (включая внешнюю) по одной вершине графа ''G&prime;'' и, а затем, если две области грани в <tex>G</tex> имеют общее ребро ''x'', соединим помещенные соединить ребром соответствующие им вершины в них вершины ребром ''x&prime;'<tex>G'</tex> (если грани имеют несколько общих рёбер, пересекающим только ''x''соответствующие вершины следует соединить несколькими параллельными рёбрами). В результате всегда получится плоский псевдограф. Ясно Например, что ''G&prime;'' имеет петлю тогда и только тогдасуществуют графы, когда в ''G'' есть концевая вершина; ''G&prime;'' имеет кратные рёбра тогда и только тогда, когда две области графа ''G'' содержат по крайней мере два общих ребра. Таким образом, двусвязный плоский граф имеет всегда в качестве двойственного или граф или мультиграф, в то время как двойственный граф трёхсвязного плоского графа всегда представляет собой граф. Другими примерами двойственных графов являются платоновы графыдвойственные себе: тетраэдр — самодвойственный граф, куб и октаэдр — двойственные, так же как додекаэдр <tex>K_1</tex> и икосаэдр…»<reftex>''Харари, Ф.'' Теория графов. — М.: Книжный дом «ЛИБРОКОМ», 2009. — С. 138. — ISBN 978­-5­-397­-00622­-4.K_4</reftex>.Далее мы убедимся, что среди полных графов только они обладают таким свойством. 

[[Файл: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>* Мультиграф, ''двойственный'' к дереву, — цветок.

|neat=neat|definition=Планарный граф называется '''самодвойственным'''(англ. ''self-dual graph''), если он изоморфен своему двойственному графу.

<div style{|align="center" |-valign='float"top" |[[Файл:Wheel8_new2.png|500px|thumb|left;'|Колесо и двойственный ему граф {{---}} тоже колесо.]] |[[Файл:K4_new.png|250px|thumb|right|<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 = \fracdfrac{E}{2} + 1</tex>.<br/>В полном графе <tex>E = \fracdfrac{V \dot 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/>Таким образом, чтобы ''полный'' граф был ''самодвойственным'', в нём должна быть ровно '''одна''' или '''четыре''' вершины.