Теорема Поша - История изменений

Maintenance script: rollbackEdits.php mass rollback

2022-09-04T16:42:32Z

rollbackEdits.php mass rollback

185.244.195.157 в 03:26, 1 сентября 2022

2022-09-01T03:26:01Z

Shersh: /* Источники информации */ категория

2015-09-08T17:50:02Z

‎Источники информации: категория

NikitaMarkovnikov в 15:27, 7 ноября 2014

2014-11-07T15:27:56Z

NikitaMarkovnikov в 22:19, 6 ноября 2014

2014-11-06T22:19:15Z

NikitaMarkovnikov в 18:53, 6 ноября 2014

2014-11-06T18:53:46Z

NikitaMarkovnikov в 18:05, 6 ноября 2014

2014-11-06T18:05:00Z

NikitaMarkovnikov в 21:32, 11 октября 2014

2014-10-11T21:32:15Z

NikitaMarkovnikov в 21:29, 11 октября 2014

2014-10-11T21:29:21Z

NikitaMarkovnikov в 21:03, 11 октября 2014

2014-10-11T21:03:09Z

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

← Предыдущая		Версия 03:26, 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 Майкл Наки].
		+	\|}
		+
	==Теорема==		==Теорема==

← Предыдущая		Версия 17:50, 8 сентября 2015
Строка 70:		Строка 70:
	[[Категория: Алгоритмы и структуры данных]]		[[Категория: Алгоритмы и структуры данных]]
	[[Категория: Обходы графов]]		[[Категория: Обходы графов]]
		+	[[Категория: Гамильтоновы графы]]

@@ Строка 49: / Строка 49: @@
 |statement =
 Если <tex> n \geqslant 3 </tex> и <tex> \deg u + \deg v  \geqslant n </tex> для любой пары <tex> u </tex> и <tex> v </tex> несмежных вершин графа <tex> G </tex>, то <tex> G </tex> {{---}} гамильтонов граф.
 }}
@@ Строка 58: / Строка 56: @@
 |statement =
 Если <tex> n > 3 </tex> и <tex> \deg v  \geqslant n/2 </tex> для любой вершины <tex> v </tex> графа <tex> G </tex>, то <tex> G </tex> {{---}} гамильтонов граф.
 }}

@@ Строка 8: / Строка 8: @@
 |statement = Пусть граф <tex> G </tex> имеет <tex>n \geqslant 3</tex> вершин и выполнены следующие два условия:
-*для всякого <tex>k,\, 1 \leqslant k < (n-1)/2</tex>, число вершин со степенями, не превосходящими <tex>k</tex>, меньше чем <tex>k</tex>;
+*<tex> \forall </tex> <tex>k,\, 1 \leqslant k < (n-1)/2</tex>, число вершин со степенями, не превосходящими <tex>k</tex>, меньше чем <tex>k</tex>
-*для нечетного <tex>n</tex> число вершин степени <tex>(n-1)/2</tex> не превосходит <tex>(n-1)/2</tex>,
+*для нечетного <tex>n</tex> число вершин степени <tex>(n-1)/2</tex> не превосходит <tex>(n-1)/2</tex>
 тогда <tex> G </tex> {{---}} [[Гамильтоновы графы|гамильтонов]] граф.
 |proof =
-[[Файл: Graph-Posha.png|500px|thumb|right|]]
+[[Файл: Graph-Posha.png|500px|thumb|right|Гамильтонов цикл <tex> v_{1} v_{2} \dotsc v_{{i}_{j-1}} v_{n} v_{n-1} \dotsc v_{{i}_{j}} v_{1} </tex>]]
 Предположим, что теорема неверна. Пусть <tex> G </tex> {{---}} максимальный негамильтонов граф с <tex> n </tex> вершинами, удовлетворяющий условиям теоремы.
@@ Строка 30: / Строка 30: @@
 ==Замечания==
 [[Файл: Graph-Posha-Cubic.png|250px|thumb|right|Кубический гамильтонов граф]]
-*Приведенное достаточное условие не является необходимым. Изображенный на рисунке кубический граф гамильтонов, хотя ясно, что он не удовлетворяет условиям теоремы.
+*Приведенное достаточное условие не является необходимым. Изображенный на рисунке кубический граф {{---}} гамильтонов, хотя ясно, что он не удовлетворяет условиям теоремы.
 *Условия теоремы нельзя улучшить, так как при их ослаблении новое условие уже не будет достаточным для гамильтоновости графа.
@@ Строка 50: / Строка 50: @@
 Если <tex> n \geqslant 3 </tex> и <tex> \deg u + \deg v  \geqslant n </tex> для любой пары <tex> u </tex> и <tex> v </tex> несмежных вершин графа <tex> G </tex>, то <tex> G </tex> {{---}} гамильтонов граф.
 |proof =
-Возьмем две любые несмежные вершины <tex> u </tex> и <tex> v </tex>. Пусть <tex> \deg u = k </tex>. Тогда <tex> \deg v \geqslant n - k </tex>. Возьмем <tex> k </tex> как в теореме Поша. Тогда, учитывая ограничения теоремы и что вершины не смежны, получаем, что следствие верно.
+Возьмем две любые несмежные вершины <tex> u </tex> и <tex> v </tex>. Пусть <tex> \deg u = k </tex>. Тогда <tex> \deg v \geqslant n - k </tex>. Возьмем <tex> k </tex> как в условии теоремы Поша. Тогда, учитывая ограничения теоремы и что вершины несмежны, получаем, что следствие верно.
 }}
@@ Строка 59: / Строка 59: @@
 Если <tex> n > 3 </tex> и <tex> \deg v  \geqslant n/2 </tex> для любой вершины <tex> v </tex> графа <tex> G </tex>, то <tex> G </tex> {{---}} гамильтонов граф.
 |proof =
-Возьмем любые несмежные вершины <tex> u, v \in G </tex>.
+Возьмем любые несмежные вершины <tex> u, v \in G </tex>. Тогда <tex> \displaystyle \deg u + \deg v \geqslant \frac n 2 + \frac n 2 = n </tex>. По теореме Оре <tex> G </tex> {{---}} гамильтонов граф.
 }}

← Предыдущая		Версия 21:32, 11 октября 2014
Строка 32:		Строка 32:
	*Приведенное достаточное условие не является необходимым. Изображенный на рисунке кубический граф гамильтонов, хотя ясно, что он не удовлетворяет условиям теоремы.		*Приведенное достаточное условие не является необходимым. Изображенный на рисунке кубический граф гамильтонов, хотя ясно, что он не удовлетворяет условиям теоремы.
	*Условия теоремы нельзя улучшить, так как при их ослаблении новое условие уже не будет достаточным для гамильтоновости графа.		*Условия теоремы нельзя улучшить, так как при их ослаблении новое условие уже не будет достаточным для гамильтоновости графа.
		+

@@ Строка 71: / Строка 71: @@
 *[[Теорема Редеи-Камиона]]
-==Источники==
+==Источники информации==
 *Харари Ф. Теория графов: Пер. с англ. / Предисл. В. П. Козырева; Под ред. Г.П.Гаврилова. Изд. 4-е. — М.: Книжный дом "ЛИБРОКОМ", 2009. — 60 с.
 [[Категория: Алгоритмы и структуры данных]]
 [[Категория: Обходы графов]]

@@ Строка 17: / Строка 17: @@
 Предположим, что теорема неверна. Пусть <tex> G </tex> {{---}} максимальный негамильтонов граф с <tex> n </tex> вершинами, удовлетворяющий условиям теоремы.
-Легко видеть, что добавление любого ребра в граф, обладающий указанными свойствами, приводит к графу, который также обладает этими свойствами. Таким образом, поскольку добавление к <tex> G </tex> произвольного ребра приводит к гамильтонову ребру, любые две несмежные вершины соединимы простой остовной цепью.
+Легко видеть, что добавление любого ребра в граф, обладающий указанными свойствами, приводит к графу, который также обладает этими свойствами. Таким образом, поскольку добавление к <tex> G </tex> произвольного ребра приводит к гамильтонову графу, любые две несмежные вершины соединимы простым гамильтоновым путем.
-Покажем сначала, что всякая вершина, степень которой не меньше <tex> (n-1)/2 </tex>, смежна с каждой вершиной со степенью, большей чем <tex> (n-1)/2 </tex>. Не умаляя общности, допустим, что <tex> \deg v_{1} \geqslant (n-1)/2 </tex> и <tex> \deg v_{n} \geqslant n/2 </tex>, но вершины <tex> v_{1} </tex> и <tex> v_{n} </tex> не смежны. Тогда существует простая остовная цепь <tex> v_{1} v_{2} \dotsc v_{n} </tex>, соединяющая <tex> v_{1} </tex> и <tex> v_{n} </tex>. Обозначим вершины, смежные с <tex> v_{1} </tex>, через <tex> v_{{i}_{1}}, \dotsc,v_{{i}_{k}} </tex>, где <tex> k = \deg v_{1} </tex> и <tex> 2=i_{1} < i_{2} < \dotsc < i_{k} </tex>. Ясно, что вершина <tex> v_{n} </tex> не может быть смежной ни с одной вершиной из <tex> G </tex> вида <tex> v_{{i}_{j-1}} </tex>, поскольку тогда в <tex> G </tex> был бы гамильтонов цикл <tex> v_{1} v_{2} \dotsc v_{{i}_{j-1}} v_{n} v_{n-1} \dotsc v_{{i}_{j}} v_{1} </tex>.
+Покажем сначала, что всякая вершина, степень которой не меньше <tex> (n-1)/2 </tex>, смежна с каждой вершиной со степенью, большей чем <tex> (n-1)/2 </tex>. Не умаляя общности, допустим, что <tex> \deg v_{1} \geqslant (n-1)/2 </tex> и <tex> \deg v_{n} \geqslant n/2 </tex>, но вершины <tex> v_{1} </tex> и <tex> v_{n} </tex> не смежны. Тогда существует простой гамильтонов путь <tex> v_{1} v_{2} \dotsc v_{n} </tex>, соединяющий <tex> v_{1} </tex> и <tex> v_{n} </tex>. Обозначим вершины, смежные с <tex> v_{1} </tex>, через <tex> v_{{i}_{1}}, \dotsc,v_{{i}_{k}} </tex>, где <tex> k = \deg v_{1} </tex> и <tex> 2=i_{1} < i_{2} < \dotsc < i_{k} </tex>. Ясно, что вершина <tex> v_{n} </tex> не может быть смежной ни с одной вершиной из <tex> G </tex> вида <tex> v_{{i}_{j-1}} </tex>, поскольку тогда в <tex> G </tex> был бы гамильтонов цикл <tex> v_{1} v_{2} \dotsc v_{{i}_{j-1}} v_{n} v_{n-1} \dotsc v_{{i}_{j}} v_{1} </tex>.
 Далее, так как <tex> k \geqslant (n-1)/2 </tex>, то <tex> n/2 \leqslant \deg v_{n} \leqslant n-1-k < n/2 </tex>, что невозможно. Поэтому <tex> v_{1} </tex> и <tex> v_{n} </tex> должны быть смежны.
@@ Строка 25: / Строка 25: @@
 Отсюда следует, что если <tex> \deg v \geqslant n/2 </tex> для всех вершин <tex> v </tex>, то <tex> G </tex> {{---}} гамильтонов граф. В силу изложенного выше каждая пара вершин графа <tex> G </tex> смежна, т.е. <tex> G </tex> {{---}} полный граф. Мы пришли к противоречию, поскольку <tex> K_{n} </tex> {{---}} гамильтонов граф для всех <tex> n \geqslant 3 </tex>.
-Таким образом, в <tex> G </tex> есть вершина <tex> v </tex> с <tex> \deg v < n/2 </tex>. Обозначим через <tex> m </tex> наибольшую среди степеней всех таких вершин. Выберем такую вершину <tex> v_{1} </tex>, что <tex> \deg v_{1} = m </tex>. По принятому предположению число вершин со степенями, не превосходящими <tex> m </tex>, не больше чем <tex> m < n/2 </tex>, поэтому должно быть более чем <tex> m </tex> вершин со степенями, превосходящими <tex> m </tex>, и, следовательно, не меньшими чем <tex> n/2 </tex>. В результате найдется некоторая вершина, скажем <tex> v_{n} </tex>, степени по крайней мере <tex> n/2 </tex>, не смежная с <tex> v_{1} </tex>. Так как <tex> v_{1} </tex> и <tex> v_{n} </tex> не смежны, то существует остовная простая цепь <tex> v_{1} \dotsc v_{n} </tex>. Как и выше, обозначим через <tex> v_{{i}_{1}}, \dotsc, v_{{i}_{m}} </tex> вершины графа <tex> G </tex>, смежные с <tex> v_{1} </tex>, и заметим, что вершина <tex> v_{n} </tex> не может быть смежной ни с одной из <tex> m </tex> вершин <tex> v_{{i}_{j-1}} </tex> для <tex> 1 \leqslant j \leqslant m </tex>. Но поскольку <tex> v_{1} </tex> и <tex> v_{n} </tex> не смежны, а <tex> v_{n} </tex> имеет степень не меньше <tex> n/2 </tex>, то, как было показано в первой части доказательства, <tex> m </tex> должно быть меньше чем <tex> (n-1)/2 </tex>. Так как по предположению число вершин со степенями, не превосходящими <tex> m </tex>, меньше чем <tex> m </tex>, то хотя бы одна из <tex> m </tex> вершин <tex> v_{{i}_{j-1}} </tex>, скажем <tex> v' </tex>, должна иметь степень не меньше <tex> n/2 </tex>. Итак, мы установили, что степени двух несмежных вершин <tex> v_{n} </tex> и <tex> v' </tex> не меньше <tex> n/2 </tex>. Полученное противоречие завершает доказательство теоремы.
+Таким образом, в <tex> G </tex> есть вершина <tex> v </tex> с <tex> \deg v < n/2 </tex>. Обозначим через <tex> m </tex> наибольшую среди степеней всех таких вершин. Выберем такую вершину <tex> v_{1} </tex>, что <tex> \deg v_{1} = m </tex>. По принятому предположению число вершин со степенями, не превосходящими <tex> m </tex>, не больше чем <tex> m < n/2 </tex>, поэтому должно быть более чем <tex> m </tex> вершин со степенями, превосходящими <tex> m </tex>, и, следовательно, не меньшими чем <tex> n/2 </tex>. В результате найдется некоторая вершина, скажем <tex> v_{n} </tex>, степени по крайней мере <tex> n/2 </tex>, не смежная с <tex> v_{1} </tex>. Так как <tex> v_{1} </tex> и <tex> v_{n} </tex> не смежны, то существует простой гамильтонов путь <tex> v_{1} \dotsc v_{n} </tex>. Как и выше, обозначим через <tex> v_{{i}_{1}}, \dotsc, v_{{i}_{m}} </tex> вершины графа <tex> G </tex>, смежные с <tex> v_{1} </tex>, и заметим, что вершина <tex> v_{n} </tex> не может быть смежной ни с одной из <tex> m </tex> вершин <tex> v_{{i}_{j-1}} </tex> для <tex> 1 \leqslant j \leqslant m </tex>. Но поскольку <tex> v_{1} </tex> и <tex> v_{n} </tex> не смежны, а <tex> v_{n} </tex> имеет степень не меньше <tex> n/2 </tex>, то, как было показано в первой части доказательства, <tex> m </tex> должно быть меньше чем <tex> (n-1)/2 </tex>. Так как по предположению число вершин со степенями, не превосходящими <tex> m </tex>, меньше чем <tex> m </tex>, то хотя бы одна из <tex> m </tex> вершин <tex> v_{{i}_{j-1}} </tex>, скажем <tex> v' </tex>, должна иметь степень не меньше <tex> n/2 </tex>. Итак, мы установили, что степени двух несмежных вершин <tex> v_{n} </tex> и <tex> v' </tex> не меньше <tex> n/2 </tex>. Полученное противоречие завершает доказательство теоремы.
 }}