50
правок
Изменения
Нет описания правки
Граф <tex>K_5</tex> [[Укладка графа на плоскости|непланарен]].
|proof=
Граф <tex>K_5</tex> имеет <tex>5 </tex> вершин и <tex>10 </tex> ребер. Если он планарен, то по [[Формула Эйлера#EulerFormulaCons|следствию из формулы Эйлера]] получаем <tex>10 \le leqslant 3 \cdot 5 - 6 = 9</tex>. Что невозможно.
}}
{{Теорема
|proof=
Граф <tex>K_{3,3}</tex> содержит <tex>V = 6</tex>, <tex>E = 9</tex> и <tex>F</tex> [[Укладка графа на плоскости|граней]]. <br />
Пусть граф <tex>K_{3,3}</tex> планарен. Тогда по [[Формула Эйлера|формуле Эйлера]] <tex>F = E - V + 2 = 9 - 6 + 2 = 5</tex>. Пусть, двигаясь вдоль <tex>i</tex>-й грани мы пройдем <tex>l_i</tex> ребер. Очевидно, что <tex>\sum_{i=1}^{F}l_i = 2E</tex>. Поскольку граф двудольный, все его циклы имеют четную длину. Значит <tex>l_i \ge geqslant 4</tex>. Получаем <tex>4F \le leqslant 2E</tex>, то есть <tex>2F \le leqslant E</tex>. То есть <tex>2\cdot5 = 10 \le leqslant 9</tex>, что невозможно.
}}
==ЛитератураИсточники информации==* Асанов М. О., Баранский В. А., Расин В. В. {{- --}} Дискретная математика - : Графы, матроиды, алгоритмы: Учебное пособие. 2-е изд., испр. и доп. {{---}} СПб.: Издательство "Лань", 2010. {{---}} C. 134 {{---}} (Учебники для вузов. Специальная литература). ISBN 978-5-8114-1068-2* [[wikipedia:ru:Планарный граф | Википедия {{---}} Планарный граф]]* [[wikipedia:ru:Домики и колодцы | Википедия {{---}} Домики и колодцы]]
[[Категория: Алгоритмы и структуры данных]]
[[Категория: Укладки графов ]]
