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

Maintenance script: rollbackEdits.php mass rollback

2022-09-04T16:18:39Z

rollbackEdits.php mass rollback

171.25.193.80 в 05:32, 1 сентября 2022

2022-09-01T05:32:40Z

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

2015-09-08T17:52:16Z

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

AntonBorzenko в 17:40, 12 января 2015

2015-01-12T17:40:09Z

AntonBorzenko в 17:35, 12 января 2015

2015-01-12T17:35:12Z

AntonBorzenko в 17:28, 12 января 2015

2015-01-12T17:28:06Z

Igor buzhinsky в 05:06, 3 февраля 2012

2012-02-03T05:06:37Z

192.168.0.2 в 07:01, 24 сентября 2011

2011-09-24T07:01:22Z

Roman Livarsky в 02:59, 28 октября 2010

2010-10-28T02:59:29Z

Roman Livarsky в 02:11, 14 октября 2010

2010-10-14T02:11:54Z

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

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

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

@@ Строка 18: / Строка 18: @@
 Имеем: <tex>\left\vert S \right\vert + \left\vert T \right\vert = \operatorname{deg} u + \operatorname{deg} v \geqslant n </tex>, но <tex>\left\vert S + T \right\vert < n.</tex>
-Тогда <tex>\left\vert S\cap T \right\vert = \left\vert S \right\vert + \left\vert T \right\vert - \left\vert S+T \right\vert > 0</tex>, т. е. <tex>\exists i \mid ut_{i+1}\in EG</tex> и <tex> t_iv \in EG.</tex>
+Тогда <tex>\left\vert S\cap T \right\vert = \left\vert S \right\vert + \left\vert T \right\vert - \left\vert S+T \right\vert > 0</tex>, т. е. <tex>\exists i: ut_{i+1}\in EG</tex> и <tex> t_iv \in EG.</tex>
 Получили противоречие, т. к. <tex>u \dots t_1v \dots t_2u</tex> {{---}} гамильтонов цикл.
 }}

@@ Строка 1: / Строка 1: @@
 {{Теорема
 |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> {{---}} [[Гамильтоновы графы | гамильтонов граф]].
+Если <tex>n \geqslant 3</tex> и <tex>\operatorname{deg} u + \operatorname{deg} v \geqslant n</tex>  для любых двух различных несмежных вершин <tex>u</tex> и <tex>v</tex> [[Основные определения теории графов#Неориентированные графы|неориентированного графа]]  <tex>G</tex>, то  <tex>G</tex> {{---}} [[Гамильтоновы графы | гамильтонов граф]].
 |proof=
@@ Строка 10: / Строка 10: @@
 Пусть <tex>u,v</tex> несмежные вершины в полученном графе <tex>G'</tex>. Если добавить ребро <tex>uv</tex>, появится гамильтонов цикл. Тогда путь <tex>(u,v)</tex> {{---}} гамильтонов.
-Для вершин <tex>u,v</tex> выполнено <tex>deg\ u + deg\ v \geqslant n.</tex>
+Для вершин <tex>u,v</tex> выполнено <tex>\operatorname{deg} u + \operatorname{deg} v \geqslant n.</tex>
-По принципу Дирихле всегда найдутся две смежные вершины <tex> t_1,t_2</tex> на пути <tex>(u,v)</tex>, т.е. <tex>u..t_1t_2..v</tex> , такие, что существует ребро <tex>ut_2</tex> и ребро <tex>t_1v.</tex>
+По принципу Дирихле всегда найдутся две смежные вершины <tex> t_1,t_2</tex> на пути <tex>(u,v)</tex>, т.е. <tex>u \dots t_1t_2 \dots v</tex> , такие, что существует ребро <tex>ut_2</tex> и ребро <tex>t_1v.</tex>
 Действительно, пусть <tex>S=</tex>  <tex>\{ i \mid e_i=ut_{i+1} \in EG \}</tex> и <tex>T = </tex>  <tex>\{ i \mid f_i=t_iv \in EG \}</tex>
-Имеем: <tex>\left\vert S \right\vert + \left\vert T \right\vert = deg\ u + deg\ v \geqslant n </tex>, но <tex>\left\vert S + T \right\vert < n.</tex>
+Имеем: <tex>\left\vert S \right\vert + \left\vert T \right\vert = \operatorname{deg} u + \operatorname{deg} v \geqslant n </tex>, но <tex>\left\vert S + T \right\vert < n.</tex>
 Тогда <tex>\left\vert S\cap T \right\vert = \left\vert S \right\vert + \left\vert T \right\vert - \left\vert S+T \right\vert > 0</tex>, т. е. <tex>\exists i \mid ut_{i+1}\in EG</tex> и <tex> t_iv \in EG.</tex>
-Получили противоречие, т. к. <tex>u..t_1v..t_2u</tex> {{---}} гамильтонов цикл.
+Получили противоречие, т. к. <tex>u \dots t_1v \dots t_2u</tex> {{---}} гамильтонов цикл.
 }}
 == См. также ==
@@ Строка 25: / Строка 25: @@
 * [[Алгоритм нахождения Гамильтонова цикла в условиях теорем Дирака и Оре]]
 * [[Теорема Дирака]]
-== Источники ==
+== Источники информации ==
 * Асанов М. О., Баранский В. А., Расин В. В. {{---}} Дискретная математика: Графы, матроиды, алгоритмы. '''ISBN 978-5-8114-1068-2'''
 * Харари {{---}} Теория графов. '''ISBN 978-5-397-00622-4'''

@@ Строка 1: / Строка 1: @@
 {{Теорема
 |statement=
-Если <tex>n \ge  3</tex> и <tex>deg\ u + deg\ v \ge n</tex>  для любых двух различных несмежных вершин <tex>u</tex> и <tex>v</tex> неориентированного графа  <tex>G</tex>, то  <tex>G</tex> - гамильтонов граф.
+Если <tex>n \ge  3</tex> и <tex>deg\ u + deg\ v \ge n</tex>  для любых двух различных несмежных вершин <tex>u</tex> и <tex>v</tex> неориентированного графа  <tex>G</tex>, то  <tex>G</tex> {{---}} гамильтонов граф.
 |proof=
@@ Строка 8: / Строка 8: @@
 Будем добавлять к нему новые ребра до тех пор, пока не получим максимальный негамильтонов граф <tex>G'</tex>. В силу того, что мы только добавляли ребра, условие теоремы не нарушилось.
-Пусть <tex>u,v</tex> несмежные вершины в полученном графе <tex>G'</tex>. Если добавить ребро <tex>uv</tex>, появится гамильтонов цикл. Тогда путь <tex>(u,v)</tex> - гамильтонов.
+Пусть <tex>u,v</tex> несмежные вершины в полученном графе <tex>G'</tex>. Если добавить ребро <tex>uv</tex>, появится гамильтонов цикл. Тогда путь <tex>(u,v)</tex> {{---}} гамильтонов.
 Для вершин <tex>u,v</tex> выполнено <tex>deg\ u + deg\ v \ge n.</tex>
-По принципу Дирихле всегда найдутся две смежные вершины <tex> t_1,t_2</tex> на пути <tex>(u,v)</tex> ,т.е. <tex>u..t_1t_2..v</tex> , такие, что существует ребро <tex>ut_2</tex> и ребро <tex>t_1v.</tex>
+По принципу Дирихле всегда найдутся две смежные вершины <tex> t_1,t_2</tex> на пути <tex>(u,v)</tex>, т.е. <tex>u..t_1t_2..v</tex> , такие, что существует ребро <tex>ut_2</tex> и ребро <tex>t_1v.</tex>
 Действительно, пусть <tex>S=</tex> { <tex> i| e_i=ut_{i+1} \in EG</tex> } и <tex>T = </tex> { <tex> i| f_i=t_iv \in EG</tex> }
@@ Строка 19: / Строка 19: @@
 Тогда <tex>\left\vert S\cap T \right\vert = \left\vert S \right\vert + \left\vert T \right\vert - \left\vert S+T \right\vert > 0</tex> т.е. <tex>\exists i| ut_{i+1}\in EG</tex> и <tex> t_iv \in EG.</tex>
-Получили противоречие, т.к. <tex>u..t_1v..t_2u</tex> - гамильтонов цикл.
+Получили противоречие, т.к. <tex>u..t_1v..t_2u</tex> {{---}} гамильтонов цикл.
 }}
 == Источники ==
-. Асанов М. О., Баранский В. А., Расин В. В. - Дискретная математика: Графы, матроиды, алгоритмы. '''ISBN 978-5-8114-1068-2'''<br />
+. Асанов М. О., Баранский В. А., Расин В. В. {{---}} Дискретная математика: Графы, матроиды, алгоритмы. '''ISBN 978-5-8114-1068-2'''<br />
-. Харари Ф. - Теория графов. '''ISBN 978-5-397-00622-4'''
+. Харари {{---}} Теория графов. '''ISBN 978-5-397-00622-4'''
 [[Категория: Алгоритмы и структуры данных]]
 [[Категория: Обходы графов]]

← Предыдущая		Версия 07:01, 24 сентября 2011
Строка 25:		Строка 25:
	1. Асанов М. О., Баранский В. А., Расин В. В. - Дискретная математика: Графы, матроиды, алгоритмы. '''ISBN 978-5-8114-1068-2'''<br />		1. Асанов М. О., Баранский В. А., Расин В. В. - Дискретная математика: Графы, матроиды, алгоритмы. '''ISBN 978-5-8114-1068-2'''<br />
	2. Харари Ф. - Теория графов. '''ISBN 978-5-397-00622-4'''		2. Харари Ф. - Теория графов. '''ISBN 978-5-397-00622-4'''
		+
		+
		+	[[Категория: Алгоритмы и структуры данных]]
		+	[[Категория: Обходы графов]]

← Предыдущая		Версия 02:59, 28 октября 2010
Строка 21:		Строка 21:
	Получили противоречие, т.к. <tex>u..t_1v..t_2u</tex> - гамильтонов цикл.		Получили противоречие, т.к. <tex>u..t_1v..t_2u</tex> - гамильтонов цикл.
	}}		}}
		+
		+	== Источники ==
		+	1. Асанов М. О., Баранский В. А., Расин В. В. - Дискретная математика: Графы, матроиды, алгоритмы. '''ISBN 978-5-8114-1068-2'''<br />
		+	2. Харари Ф. - Теория графов. '''ISBN 978-5-397-00622-4'''

@@ Строка 1: / Строка 1: @@
 {{Теорема
 |statement=
-Если <math>n \ge  3</math> и <math>deg\ u + deg \ v \ge n</math>  для любых двух различных несмежных вершин <math>\ u</math> и <math>\ v</math> неориентированного графа  '''G''', то  '''G''' - гамильтонов граф.
+Если <tex>n \ge  3</tex> и <tex>deg\ u + deg\ v \ge n</tex>  для любых двух различных несмежных вершин <tex>u</tex> и <tex>v</tex> неориентированного графа  <tex>G</tex>, то  <tex>G</tex> - гамильтонов граф.
 |proof=
-Пусть, от противного, существует граф '''G''', который удовлетворяет условию теоремы, но не является гамильтоновым графом.
+Пусть, от противного, существует граф <tex>G</tex>, который удовлетворяет условию теоремы, но не является гамильтоновым графом.
-Будем добавлять к нему новые ребра до тех пор, пока не получим максимальный негамильтонов граф '''G''''. В силу того, что мы только добавляли ребра, условие теоремы не нарушилось.
+Будем добавлять к нему новые ребра до тех пор, пока не получим максимальный негамильтонов граф <tex>G'</tex>. В силу того, что мы только добавляли ребра, условие теоремы не нарушилось.
-Пусть <math>\ u,v</math> несмежные вершины в полученном графе '''G''''. Если добавить ребро <math>\ uv</math>, появится гамильтонов цикл. Тогда путь <math>\ (u,v)</math> - гамильтонов.
+Пусть <tex>u,v</tex> несмежные вершины в полученном графе <tex>G'</tex>. Если добавить ребро <tex>uv</tex>, появится гамильтонов цикл. Тогда путь <tex>(u,v)</tex> - гамильтонов.
-Для вершин <math>\ u,v</math> выполнено <math>deg\ u + deg \ v \ge n.</math>
+Для вершин <tex>u,v</tex> выполнено <tex>deg\ u + deg\ v \ge n.</tex>
-По принципу Дирихле всегда найдутся две смежные вершины <math>\ t_1,t_2</math> на пути <math>\ (u,v)</math> ,т.е. <math>\ u..t_1t_2..v</math> , такие, что существует ребро <math>\ ut_2</math> и ребро <math>\ t_1v.</math>
+По принципу Дирихле всегда найдутся две смежные вершины <tex> t_1,t_2</tex> на пути <tex>(u,v)</tex> ,т.е. <tex>u..t_1t_2..v</tex> , такие, что существует ребро <tex>ut_2</tex> и ребро <tex>t_1v.</tex>
-Действительно, пусть <math>\ S = </math> { <math> i| e_i=ut_{i+1} \in EG</math> } и <math>\ T = </math> { <math> i| f_i=t_iv \in EG</math> }
+Действительно, пусть <tex>S=</tex> { <tex> i| e_i=ut_{i+1} \in EG</tex> } и <tex>T = </tex> { <tex> i| f_i=t_iv \in EG</tex> }
-Имеем: <math>\left\vert S \right\vert + \left\vert T \right\vert = deg\ u + deg \ v \ge n </math>, но <math>\left\vert S + T \right\vert < n.</math>
+Имеем: <tex>\left\vert S \right\vert + \left\vert T \right\vert = deg\ u + deg\ v \ge n </tex>, но <tex>\left\vert S + T \right\vert < n.</tex>
-Тогда <math>\left\vert S\cap T \right\vert = \left\vert S \right\vert + \left\vert T \right\vert - \left\vert S+T \right\vert > 0</math> т.е. <math>\exists i| ut_{i+1}\in EG</math> и <math> t_iv \in EG.</math>
+Тогда <tex>\left\vert S\cap T \right\vert = \left\vert S \right\vert + \left\vert T \right\vert - \left\vert S+T \right\vert > 0</tex> т.е. <tex>\exists i| ut_{i+1}\in EG</tex> и <tex> t_iv \in EG.</tex>
-Получили противоречие, т.к. <math>\ u..t_1v..t_2u</math> - гамильтонов цикл.
+Получили противоречие, т.к. <tex>u..t_1v..t_2u</tex> - гамильтонов цикл.
 }}