Изменения

Перейти к: навигация, поиск

Двойственный граф планарного графа

113 байт добавлено, 07:58, 18 октября 2010
Нет описания правки
}}
<div style='clear:left;'></div>
[[Файл:K4.png|thumb|left|<tex>K_4</tex> (он же кольцо).]]
[[Файл:Wheel_8.png|thumb|left|Колесо и колесо.]]
[[Файл:K4.png|thumb|right|<tex>K_4</tex> (он же кольцо).]]
* <div style='float:left;'>{{Утверждение|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 = \frac{E}{2} + 1</tex>.<br/>В полном графе <tex>E = \frac{V \dot (V - 1)}{2}</tex>.<br/>Получаем квадратное уравнение: <tex>V^2 - 5V + 4 = 0</tex>.<br/>Его решения: <tex>V_1 = 1</tex> и <tex>V_2 = 4</tex>.<br/>Таким образом, чтобы ''полный'' граф был ''самодвойственным'', в нём должна быть ровно '''одна''' или '''четыре''' вершины.}}
Подставив в [[Формула Эйлера|формулу Эйлера]] имеем: <tex>2V div style= E + 2 \Leftrightarrow V = \frac{E}{2} + 1</tex>. В полном графе <tex>E = \frac{V \dot (V - 1)}{2}</tex>. Получаем квадратное уравнение'clear: <tex>V^2 - 5V + 4 = 0</tex>. Его решения: <texboth;'>V_1 = 1<br/tex> и <tex>V_2 = 4</texdiv>.Таким образом, чтобы ''полный'' граф был ''самодвойственным'', в нём должна быть ровно '''одна''' или '''четыре''' вершины.}}* {{Утверждение|neat=neat
|statement=Все колёса самодвойственны.
}}
</div>
<div style="clear:both;"></div>

Навигация