Панциклический граф - История изменений

Maintenance script: rollbackEdits.php mass rollback

2022-09-04T16:34:07Z

rollbackEdits.php mass rollback

88.208.225.209 в 04:20, 1 сентября 2022

2022-09-01T04:20:06Z

Alex PKZDL: добавлена лемма о четности n

2017-12-26T13:41:46Z

добавлена лемма о четности n

Alex PKZDL: pictures fixed

2017-12-26T13:32:36Z

pictures fixed

217.66.152.83 в 16:42, 24 декабря 2017

2017-12-24T16:42:28Z

217.66.152.83 в 16:26, 24 декабря 2017

2017-12-24T16:26:01Z

Alex PKZDL: 0.2.1.0:0.2.1.0:0.1:1.0.0

2017-12-20T09:55:14Z

0.2.1.0:0.2.1.0:0.1:1.0.0

217.66.159.65: разбил докво

2017-12-18T17:17:35Z

разбил докво

217.66.152.76: /* Следствие */

2017-12-18T11:37:24Z

‎Следствие

Alex PKZDL: thumb + text picture 3

2017-12-18T10:04:28Z

thumb + text picture 3

← Предыдущая		Версия 16:34, 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 Майкл Наки].
−	\|}
−
	== Основные определения ==		== Основные определения ==
	{{Определение		{{Определение

← Предыдущая		Версия 04:20, 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 Майкл Наки].
		+	\|}
		+
	== Основные определения ==		== Основные определения ==
	{{Определение		{{Определение

@@ Строка 33: / Строка 33: @@
 Значит в <tex> G </tex> может входить максимум одно ребро из таких пар. Тогда можно утверждать, что <tex> deg(v_j) + deg(v_{j + 1}) \leqslant n </tex>.
-Докажем методом от противного, что <tex> n </tex> {{---}} четно.
+{{Лемма
 *Пусть <tex> n </tex> является нечетным, тогда из рассуждений выше существует вершина <tex> v_x </tex>, для которое верно, что  <tex> deg(v_x) \leqslant \genfrac{}{}{}{0}{n-1}{2} </tex>.
 **Пусть это не так, тогда <tex> \forall i, 1 \leqslant i \leqslant n : deg(v_i) \geqslant \genfrac{}{}{}{0}{n-1}{2} + 1 = \genfrac{}{}{}{0}{n+1}{2} </tex>, значит <tex> \forall j, 1 \leqslant j \leqslant n : deg(v_j) + deg(v_{j+1}) \geqslant \genfrac{}{}{}{0}{n+1}{2} + \genfrac{}{}{}{0}{n+1}{2} = n + 1 </tex>, то есть мы получили противоречие с тем, что <tex> deg(v_j) + deg(v_{j + 1}) \leqslant n </tex>.
 *Без потери общности пусть <tex> v_x = v_n </tex>. Рассмотрим <tex> 2|E| = \sum\limits_{i=1}^n deg(v_i) =  \sum\limits_{i=1}^{\genfrac{}{}{}{}{n - 1}{2}} (deg(v_{2i-1}) + deg(v_{2i})) + deg(v_n) \leqslant \genfrac{}{}{}{0}{n(n-1)}{2} + </tex> <tex> \genfrac{}{}{}{0}{n-1}{2} < \genfrac{}{}{}{0}{n^2}{2} </tex>, то есть <tex> |E| < \genfrac{}{}{}{0}{n^2}{4} </tex>, но по условию <tex> |E| \geqslant \genfrac{}{}{}{0}{n^2}{4} </tex>  {{---}} получили противоречие.
-Таким образом <tex> n </tex> является четным, если в цикле отсутствует цикл длины <tex> l </tex>. Тогда верно, что <tex> 2|E| = \sum\limits_{i=1}^n deg(v_i) =  \sum\limits_{i=1}^{\genfrac{}{}{}{}{n}{2}} (deg(v_{2i-1}) + deg(v_{2i})) \leqslant \genfrac{}{}{}{0}{n^2}{2} </tex>, а так как по условию <tex> |E| \geqslant \genfrac{}{}{}{0}{n^2}{4} </tex>, то <tex> |E| = \genfrac{}{}{}{0}{n^2}{4} </tex>. Данное равенство достигается, если верно, что:
+}}
 [[Файл:Circle 3.jpg|800px|right|thumb|Слева направо изображены случаи 1-3. Красным выделены ребра, которые не могут быть в рассматриваемом графе, если в нем присутствуют ребра, выделенные зеленым]]

@@ Строка 18: / Строка 18: @@
 |proof=
-[[Файл:Circle 1.jpg|200px|left|thumb| Дуги и ребра, окрашенные в зеленый цвет, образуют цикл длины l]] [[Файл:Circle 2.jpg|200px|right|thumb| Дуги и ребра, окрашенные в зеленый цвет, образуют цикл длины l]]
+[[Файл:Circle 1.jpg|200px|left|thumb| <tex> v_k </tex> на дуге <tex> (v_{j + l - 1}, v_{j + l}, v_{j -1}) </tex> и ребра (<tex>v_j, v_k</tex>) и  (<tex>v_{j+1}, v_{k-l+3}</tex>) выделены. Дуги и ребра, окрашенные в зеленый цвет, образуют цикл длины l]] [[Файл:Circle 2.jpg|200px|right|thumb| <tex> v_k </tex> на дуге <tex> (v_{j + 2}, v_{j + 3}, v_{j + l - 2}) </tex> и ребра (<tex>v_j, v_k</tex>) и  (<tex>v_{j+1}, v_{k-l+1}</tex>) выделены. Дуги и ребра, окрашенные в зеленый цвет, образуют цикл длины l]]
-Обозначим как <tex> C=v_1 v_2 v_3 \ldots v_n </tex> гамильтонов цикл в графе <tex> G </tex>. Для простоты расположим <tex> C </tex> на окружности (см. рисунки). Также подразумевается, что все индексы при вершинах берутся по модулю, то есть <tex> v_j = v_{((j - 1)\bmod n) + 1} </tex>.
+Обозначим как <tex> C=v_1 v_2 v_3 \ldots v_n </tex> гамильтонов цикл в графе <tex> G </tex>. Для простоты расположим <tex> C </tex> на окружности. Также подразумевается, что все индексы при вершинах берутся по модулю, то есть <tex> v_j = v_{((j - 1)\bmod n) + 1} </tex>.
 Пусть граф не панциклический, тогда в неи нет цикла длины <tex> l </tex>, <tex> 3 \leqslant l \leqslant n-1 </tex> (по условию в графе существует гамильтонов цикл, длина которого равна <tex> n </tex>). Рассмотрим две соседние вершины <tex> v_j v_{j+1} </tex> и вместе с ними рассмотрим следующие пары:
-Для <tex>k</tex> таких, что <tex> v_k </tex> лежит на дуге <tex> (v_{j + l - 1}, v_{j + l}, v_{j -1}) </tex> рассмотрим пары (<tex>v_j, v_k</tex>) и (<tex>v_{j+1}, v_{k-l+3}</tex>) (см. рисунок слева)
+Для <tex>k</tex> таких, что <tex> v_k </tex> лежит на дуге <tex> (v_{j + l - 1}, v_{j + l}, v_{j -1}) </tex> рассмотрим пары (<tex>v_j, v_k</tex>) и (<tex>v_{j+1}, v_{k-l+3}</tex>)
-Для <tex>k</tex> таких, что <tex> v_k </tex> лежит на дуге <tex> (v_{j + 2}, v_{j + 3}, v_{j + l - 2}) </tex> рассмотрим пары (<tex>v_j, v_k</tex>) и (<tex>v_{j+1}, v_{k-l+1}</tex>) (см. рисунок справа)
+Для <tex>k</tex> таких, что <tex> v_k </tex> лежит на дуге <tex> (v_{j + 2}, v_{j + 3}, v_{j + l - 2}) </tex> рассмотрим пары (<tex>v_j, v_k</tex>) и (<tex>v_{j+1}, v_{k-l+1}</tex>)
-При добавлении таких пар ребер в графе появляется цикл длины <tex> l </tex> (выделены зеленым цветом на рисунках слева и справа). Действительно:
+При добавлении таких пар ребер в графе появляется цикл длины <tex> l </tex>. Действительно:
 *Рассмотрим первый случай, когда <tex> v_k </tex> лежит на дуге <tex> (v_{j + l - 1}, v_{j + l}, v_{j -1}) </tex> и существуют ребра (<tex>v_j, v_k</tex>) и (<tex>v_{j+1}, v_{k-l+3}</tex>). Длина цикла равна <tex> len((v_{k - l + 3}, v_{k - l + 4}, v_{k})) + 3 = k - (k - l + 3) + 3 =  l - 3 + 3 = l </tex>.
 *Рассмотрим второй случай, когда <tex> v_k </tex> лежит на дуге <tex> (v_{j + 2}, v_{j + 3}, v_{j + l - 2}) </tex> и существуют ребра (<tex>v_j, v_k</tex>) и (<tex>v_{j+1}, v_{k-l+1}</tex>). Тогда длина цикла равна <tex> len((v_{k}, v_{k - 1}, v_{k - l + 1})) - 1 + 2 = k - (k - l + 1) - 1 + 2 =  l - 1 - 1 + 2 = l </tex>.

@@ Строка 41: / Строка 41: @@
 [[Файл:Circle 3.jpg|800px|right|thumb|Слева направо изображены случаи 1-3. Красным выделены ребра, которые не могут быть в рассматриваемом графе, если в нем присутствуют ребра, выделенные зеленым]]
-*<tex> v_k </tex> лежит на дуге <tex> (v_{j + l - 1}, v_{j + l}, v_{j - 1}) </tex>: <tex> (v_j, v_k) \in E </tex> и <tex>(v_{j+1}, v_{k-l+3}) \notin E </tex>
+*<tex> v_k </tex> лежит на дуге <tex> (v_{j + l - 1}, v_{j + l}, v_{j - 1}) </tex>: <tex> (v_j, v_k) \in E </tex> и <tex>(v_{j+1}, v_{k-l+3}) \notin E </tex> или <tex> (v_j, v_k) \notin E </tex> и <tex>(v_{j+1}, v_{k-l+3}) \in E </tex>
-*<tex> v_k </tex> лежит на дуге <tex> (v_{j + 2}, v_{j + 3}, v_{j + l - 2}) </tex>: <tex>(v_j, v_k) \in E </tex> и <tex>(v_{j+1}, v_{k-l+1}) \notin E </tex>
+*<tex> v_k </tex> лежит на дуге <tex> (v_{j + 2}, v_{j + 3}, v_{j + l - 2}) </tex>: <tex>(v_j, v_k) \in E </tex> и <tex>(v_{j+1}, v_{k-l+1}) \notin E </tex> или <tex>(v_j, v_k) \notin E </tex> и <tex>(v_{j+1}, v_{k-l+1}) \in E </tex>
 Пусть <tex> G </tex> не <tex>K_{\genfrac{}{}{}{}{n}{2}, \genfrac{}{}{}{}{n}{2}}</tex>, тогда существует такое четное число <tex> k </tex>, что в графе <tex> G </tex> существует ребро <tex> (v_j, v_{j+k}) </tex>, то есть существует цикл нечетной длины. Докажем, что в таком случае существует ребро <tex> (v_j, v_{j+2}) \in E </tex>. Пусть это не так и минимальное четное <tex> k </tex>, что <tex> \exists (v_j, v_{j+k}) \in E </tex> больше двух, то есть <tex> k \geqslant 4 </tex>. Тогда существует три случая:

@@ Строка 33: / Строка 33: @@
 Значит в <tex> G </tex> может входить максимум одно ребро из таких пар. Тогда можно утверждать, что <tex> deg(v_j) + deg(v_{j + 1}) \leqslant n </tex>.
-Докажем методом от противного, что <tex> n </tex> {{---}} четно. Пусть <tex> n </tex> является нечетным, тогда из рассуждений выше существует вершина <tex> v_x </tex>, для которое верно, что  <tex> deg(v_x) \leqslant \genfrac{}{}{}{0}{n-1}{2} </tex>.
+Докажем методом от противного, что <tex> n </tex> {{---}} четно.
-Пусть это не так, тогда <tex> \forall i, 1 \leqslant i \leqslant n : deg(v_i) \geqslant \genfrac{}{}{}{0}{n-1}{2} + 1 = \genfrac{}{}{}{0}{n+1}{2} </tex>, значит <tex> \forall j, 1 \leqslant j \leqslant n : deg(v_j) + deg(v_{j+1}) \geqslant \genfrac{}{}{}{0}{n+1}{2} + \genfrac{}{}{}{0}{n+1}{2} = n + 1 </tex>, то есть мы получили противоречие с тем, что <tex> deg(v_j) + deg(v_{j + 1}) \leqslant n </tex>.
+*Пусть <tex> n </tex> является нечетным, тогда из рассуждений выше существует вершина <tex> v_x </tex>, для которое верно, что  <tex> deg(v_x) \leqslant \genfrac{}{}{}{0}{n-1}{2} </tex>.
-Без потери общности пусть <tex> v_x = v_n </tex>. Рассмотрим <tex> 2|E| = \sum_{i=1}^n deg(v_i) =  \sum_{i=1}^{\genfrac{}{}{}{}{n - 1}{2}} (deg(v_{2i-1}) + deg(v_{2i})) + deg(v_n) \leqslant \genfrac{}{}{}{0}{n(n-1)}{2} + </tex> <tex> \genfrac{}{}{}{0}{n-1}{2} < \genfrac{}{}{}{0}{n^2}{2} </tex>, то есть <tex> |E| < \genfrac{}{}{}{0}{n^2}{4} </tex>, но по условию <tex> |E| \geqslant \genfrac{}{}{}{0}{n^2}{4} </tex>  {{---}} получили противоречие. Таким образом <tex> n </tex> является четным. Тогда верно, что <tex> 2|E| \leqslant \sum_{i=1}^n deg(v_i) =  \sum_{i=1}^{\genfrac{}{}{}{}{n}{2}} (deg(v_{2i-1}) + deg(v_{2i})) \leqslant \genfrac{}{}{}{0}{n^2}{2} </tex>, а так как по условию <tex> |E| \geqslant \genfrac{}{}{}{0}{n^2}{4} </tex>, то <tex> |E| = \genfrac{}{}{}{0}{n^2}{4} </tex>. Данное равенство достигается, если верно, что:
+**Пусть это не так, тогда <tex> \forall i, 1 \leqslant i \leqslant n : deg(v_i) \geqslant \genfrac{}{}{}{0}{n-1}{2} + 1 = \genfrac{}{}{}{0}{n+1}{2} </tex>, значит <tex> \forall j, 1 \leqslant j \leqslant n : deg(v_j) + deg(v_{j+1}) \geqslant \genfrac{}{}{}{0}{n+1}{2} + \genfrac{}{}{}{0}{n+1}{2} = n + 1 </tex>, то есть мы получили противоречие с тем, что <tex> deg(v_j) + deg(v_{j + 1}) \leqslant n </tex>.
 [[Файл:Circle 3.jpg|800px|right|thumb|Слева направо изображены случаи 1-3. Красным выделены ребра, которые не могут быть в рассматриваемом графе, если в нем присутствуют ребра, выделенные зеленым]]
@@ Строка 61: / Строка 63: @@
 #<tex> G </tex>  = <tex>K_{\genfrac{}{}{}{}{n}{2}, \genfrac{}{}{}{}{n}{2}}</tex>
 |proof=По [[Теорема Оре|теореме Оре]] <tex> G </tex> {{---}} гамильтонов граф. Покажем, что <tex> m \geqslant \genfrac{}{}{}{0}{n^2}{4} </tex>. Пусть <tex> k </tex> {{---}} минимальная степень вершины в графе.
-# <tex> k \geqslant \genfrac{}{}{}{}{n}{2} </tex>, тогда <tex> 2m = \sum_{i=1}^n deg(v_i) >= \sum_{i=1}^n k = k n \geqslant \genfrac{}{}{}{0}{n^2}{2} </tex>
+# <tex> k \geqslant \genfrac{}{}{}{}{n}{2} </tex>, тогда <tex> 2m = \sum\limits_{i=1}^n deg(v_i) >= \sum\limits_{i=1}^n k = k n \geqslant \genfrac{}{}{}{0}{n^2}{2} </tex>
 # <tex> k < \genfrac{}{}{}{}{n}{2} </tex>. Пусть существует <tex> x </tex> вершин, так что их степени равны <tex> k </tex>, тогда они все должны быть связаны, так как иначе мы получим противоречие с утверждением теоремы <tex> \forall (u, v) \notin E : deg(u) + deg(v) \geqslant n </tex>. Понятно, что <tex> x \leqslant k + 1 </tex>, но так как граф является гамильтоновым, то он связен, а значит <tex> x < k + 1 </tex>. Несложно заметить, что если из всех <tex> x </tex> вершин степени <tex> k </tex> провести оставшиеся ребра в одну вершину, у которой степень больше, то в графе остенется как минимум <tex> n - k - 1 </tex> вершин, степени которых как минимум <tex> n - k </tex>, поскольку должно выполняться неравенство из теоермы. Тогда можно оценить количество ребер. <br> <tex> m \geqslant \genfrac{}{}{}{0}{1}{2}((n-k-1)(n-k)+k^2+(k+1)) = \genfrac{}{}{}{0}{1}{2}(n^2 - n(2k + 1) + 2k^2 + 2k + 1) \geqslant \genfrac{}{}{}{0}{n^2+1}{4} </tex>