Непланарность K5 и K3,3 - История изменений

Maintenance script: rollbackEdits.php mass rollback

2022-09-04T16:38:09Z

rollbackEdits.php mass rollback

23.128.248.38 в 03:52, 1 сентября 2022

2022-09-01T03:52:31Z

Nikitaevg в 14:19, 3 января 2017

2017-01-03T14:19:27Z

Nikitaevg в 14:14, 3 января 2017

2017-01-03T14:14:10Z

Nikitaevg в 13:57, 3 января 2017

2017-01-03T13:57:45Z

Gfv в 22:59, 4 января 2014

2014-01-04T22:59:39Z

Slavian в 16:57, 1 января 2014

2014-01-01T16:57:15Z

Rybak в 22:15, 9 ноября 2011

2011-11-09T22:15:24Z

Tsar: /* Литература */ Поправка описки

2010-10-22T23:53:04Z

‎Литература: Поправка описки

Lebedeva.anestezia в 18:30, 21 октября 2010

2010-10-21T18:30:03Z

← Предыдущая		Версия 16:38, 4 сентября 2022
Строка 1:		Строка 1:
−	~~{\| class="wikitable" align="center" style="color: red; background-color: black; font-size: 56px; width: 800px;"~~
−	\|+
−	~~\|-align="center"~~
−	~~\|'''НЕТ ВОЙНЕ'''~~
−	~~\|-style="font-size: 16px;"~~
−	\|
−	24 февраля 2022 года российское руководство во главе с Владимиром Путиным развязало агрессивную войну против Украины. В глазах всего мира это военное преступление совершено от лица всей страны, всех россиян.
−
−	Будучи гражданами Российской Федерации, мы против своей воли оказались ответственными за нарушение международного права, военное вторжение и массовую гибель людей. Чудовищность совершенного преступления не оставляет возможности промолчать или ограничиться пассивным несогласием.
−
−	Мы убеждены в абсолютной ценности человеческой жизни, в незыблемости прав и свобод личности. Режим Путина — угроза этим ценностям. Наша задача — обьединить все силы для сопротивления ей.
−
−	Эту войну начали не россияне, а обезумевший диктатор. И наш гражданский долг — сделать всё, чтобы её остановить.
−
−	~~''Антивоенный комитет России''~~
−	~~\|-style="font-size: 16px;"~~
−	\|Распространяйте правду о текущих событиях, оберегайте от пропаганды своих друзей и близких. Изменение общественного восприятия войны - ключ к её завершению.
−	~~\|-style="font-size: 16px;"~~
−	\|[https://meduza.io/ meduza.io], [https://www.youtube.com/c/popularpolitics/videos Популярная политика], [https://novayagazeta.ru/ Новая газета], [https://zona.media/ zona.media], [https://www.youtube.com/c/MackNack/videos Майкл Наки].
−	\|}
−
	{{Теорема		{{Теорема
	\|about=		\|about=

← Предыдущая		Версия 03:52, 1 сентября 2022
Строка 1:		Строка 1:
		+	{\| class="wikitable" align="center" style="color: red; background-color: black; font-size: 56px; width: 800px;"
		+	\|+
		+	\|-align="center"
		+	\|'''НЕТ ВОЙНЕ'''
		+	\|-style="font-size: 16px;"
		+	\|
		+	24 февраля 2022 года российское руководство во главе с Владимиром Путиным развязало агрессивную войну против Украины. В глазах всего мира это военное преступление совершено от лица всей страны, всех россиян.
		+
		+	Будучи гражданами Российской Федерации, мы против своей воли оказались ответственными за нарушение международного права, военное вторжение и массовую гибель людей. Чудовищность совершенного преступления не оставляет возможности промолчать или ограничиться пассивным несогласием.
		+
		+	Мы убеждены в абсолютной ценности человеческой жизни, в незыблемости прав и свобод личности. Режим Путина — угроза этим ценностям. Наша задача — обьединить все силы для сопротивления ей.
		+
		+	Эту войну начали не россияне, а обезумевший диктатор. И наш гражданский долг — сделать всё, чтобы её остановить.
		+
		+	''Антивоенный комитет России''
		+	\|-style="font-size: 16px;"
		+	\|Распространяйте правду о текущих событиях, оберегайте от пропаганды своих друзей и близких. Изменение общественного восприятия войны - ключ к её завершению.
		+	\|-style="font-size: 16px;"
		+	\|[https://meduza.io/ meduza.io], [https://www.youtube.com/c/popularpolitics/videos Популярная политика], [https://novayagazeta.ru/ Новая газета], [https://zona.media/ zona.media], [https://www.youtube.com/c/MackNack/videos Майкл Наки].
		+	\|}
		+
	{{Теорема		{{Теорема
	\|about=		\|about=

@@ Строка 22: / Строка 22: @@
 ==Источники информации==
-* Асанов М. О., Баранский В. А., Расин В. В. {{---}} Дискретная математика: Графы, матроиды, алгоритмы: Учебное пособие. 2-е изд., испр. и доп. {{---}} СПб.: Издательство "Лань", 2010. {{---}} C. 134 {{---}} (Учебники для вузов. Специальная литература). ISBN 978-5-8114-1068-2
+* Асанов М. О., Баранский В. А., Расин В. В. {{---}} '''Дискретная математика: Графы, матроиды, алгоритмы: Учебное пособие. 2-е изд., испр. и доп.''' стр. 134 {{---}} СПб.: Издательство "Лань", 2010. {{---}} 368 с.: ил. {{---}} (Учебники для вузов. Специальная литература). ISBN 978-5-8114-1068-2
 [[Категория: Алгоритмы и структуры данных]]
 [[Категория: Укладки графов ]]

@@ Строка 16: / Строка 16: @@
 Пусть граф <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>, что невозможно.
 }}
 ==Источники информации==
 * Асанов М. О., Баранский В. А., Расин В. В. {{---}} Дискретная математика: Графы, матроиды, алгоритмы: Учебное пособие. 2-е изд., испр. и доп. {{---}} СПб.: Издательство "Лань", 2010. {{---}} C. 134 {{---}} (Учебники для вузов. Специальная литература). ISBN 978-5-8114-1068-2
 [[Категория: Алгоритмы и структуры данных]]
 [[Категория: Укладки графов ]]

@@ Строка 5: / Строка 5: @@
 Граф <tex>K_5</tex> [[Укладка графа на плоскости|непланарен]].
 |proof=
-Граф <tex>K_5</tex> имеет 5 вершин и 10 ребер. Если он планарен, то по [[Формула Эйлера#EulerFormulaCons|следствию из формулы Эйлера]] получаем <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>. Что невозможно.
 }}
 {{Теорема
@@ Строка 14: / Строка 14: @@
 |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 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>, что невозможно.
 }}
-==Литература==
+==Источники информации==
-* Асанов М., Баранский В., Расин В. - Дискретная математика - Графы, матроиды, алгоритмы
+* Асанов М. О., Баранский В. А., Расин В. В. {{---}} Дискретная математика: Графы, матроиды, алгоритмы: Учебное пособие. 2-е изд., испр. и доп. {{---}} СПб.: Издательство "Лань", 2010. {{---}} C. 134 {{---}} (Учебники для вузов. Специальная литература). ISBN 978-5-8114-1068-2
 [[Категория: Алгоритмы и структуры данных]]
 [[Категория: Укладки графов ]]

← Предыдущая		Версия 22:59, 4 января 2014
Строка 1:		Строка 1:
−	~~{{Определение~~
−	~~\|definition=~~
−	~~<tex>K_5</tex> - полный граф на 5-ти вершинах.~~
−	}}
−
−	~~{{Определение~~
−	~~\|definition=~~
−	~~<tex>K_{3,3}</tex> - полный двудольный граф на 6-ти вершинах(по 3 в каждой доле).~~
−	}}
−
	{{Теорема		{{Теорема
	\|about=		\|about=

← Предыдущая		Версия 16:57, 1 января 2014
Строка 1:		Строка 1:
		+	{{Определение
		+	\|definition=
		+	<tex>K_5</tex> - полный граф на 5-ти вершинах.
		+	}}
		+
		+	{{Определение
		+	\|definition=
		+	<tex>K_{3,3}</tex> - полный двудольный граф на 6-ти вершинах(по 3 в каждой доле).
		+	}}
		+
	{{Теорема		{{Теорема
	\|about=		\|about=