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

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

Текущая версия на 19:38, 4 сентября 2022

Теорема (Непланарность [math]K_5[/math]):
Граф [math]K_5[/math] непланарен.
Доказательство:
[math]\triangleright[/math]
Граф [math]K_5[/math] имеет [math]5[/math] вершин и [math]10[/math] ребер. Если он планарен, то по следствию из формулы Эйлера получаем [math]10 \leqslant 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 \geqslant 4[/math]. Получаем [math]4F \leqslant 2E[/math], то есть [math]2F \leqslant E[/math]. То есть [math]2\cdot5 = 10 \leqslant 9[/math], что невозможно.
[math]\triangleleft[/math]

См. также

Источники информации

  • Асанов М. О., Баранский В. А., Расин В. В. — Дискретная математика: Графы, матроиды, алгоритмы: Учебное пособие. 2-е изд., испр. и доп. стр. 134 — СПб.: Издательство "Лань", 2010. — 368 с.: ил. — (Учебники для вузов. Специальная литература). ISBN 978-5-8114-1068-2
Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Непланарность_K5_и_K3,3&oldid=85679»