Непланарность K5 и K3,3 — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
м (Литература: Поправка описки)
Строка 18: Строка 18:
  
 
==Литература==
 
==Литература==
* Асанов М,, Баранский В., Расин В. - Дискретная математика - Графы, матроиды, алгоритмы
+
* Асанов М., Баранский В., Расин В. - Дискретная математика - Графы, матроиды, алгоритмы
  
 
[[Категория: Алгоритмы и структуры данных]]
 
[[Категория: Алгоритмы и структуры данных]]
 
[[Категория: Укладки графов ]]
 
[[Категория: Укладки графов ]]

Версия 02:53, 23 октября 2010

Теорема (Непланарность [math]K_5[/math]):
Граф [math]K_5[/math] непланарен.
Доказательство:
[math]\triangleright[/math]
Граф [math]K_5[/math] имеет 5 вершин и 10 ребер. Если он планарен, то по следствию из формулы Эйлера получаем [math]10 \le 3 \cdot 5 - 6 = 9[/math]. Что невозможно.
[math]\triangleleft[/math]
Теорема (Непланарность [math]K_{3,3}[/math]):
Граф [math]K_{3,3}[/math] непланарен.
Доказательство:
[math]\triangleright[/math]

Граф [math]K_{3,3}[/math] содержит [math]V = 6[/math], [math]E = 9[/math] и [math]F[/math] граней.

Пусть граф [math]K_{3,3}[/math] планарен. Тогда по формуле Эйлера [math]F = E - V + 2 = 9 - 6 + 2 = 5[/math]. Пусть, двигаясь вдоль [math]i[/math]-й грани мы пройдем [math]l_i[/math] ребер. Очевидно, что [math]\sum_{i=1}^{F}l_i = 2E[/math]. Поскольку граф двудольный, все его циклы имеют четную длину. Значит [math]l_i \ge 4[/math]. Получаем [math]4F \le 2E[/math], то есть [math]2F \le E[/math]. То есть [math]2\cdot5 = 10 \le 9[/math], что невозможно.
[math]\triangleleft[/math]

Литература

  • Асанов М., Баранский В., Расин В. - Дискретная математика - Графы, матроиды, алгоритмы