Теорема Гуйя-Ури - История изменений

Maintenance script: rollbackEdits.php mass rollback

2022-09-04T16:34:00Z

rollbackEdits.php mass rollback

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

2022-09-01T04:19:11Z

Shersh: /* Теорема Гуйя-Ури */

2016-01-02T10:29:49Z

‎Теорема Гуйя-Ури

Shersh: /* Теорема Гуйя-Ури */

2016-01-02T10:28:36Z

‎Теорема Гуйя-Ури

Shersh: /* Лемма о длине цикла в ориентированном графе */

2016-01-02T10:27:28Z

‎Лемма о длине цикла в ориентированном графе

Анна в 08:24, 2 января 2016

2016-01-02T08:24:18Z

Анна: Новая страница: «= Теорема Гуйя-Ури = {{Определение |definition= Ориентированный сильно связный граф называется...»

2016-01-02T08:10:32Z

Новая страница: «= Теорема Гуйя-Ури = {{Определение |definition= Ориентированный сильно связный граф называется...»

Новая страница

= Теорема Гуйя-Ури =

{{Определение
|definition=
Ориентированный сильно связный граф называется '''орсвязаными'''.}}
== Лемма о длине цикла в ориентированном графе ==
{{Лемма
|about=о длине цикла в ориентированном графе
|statement= Пусть <tex>G</tex> {{---}} произвольный ориентированный граф и для каждой вершины <tex>v \in V(G)</tex> выполняется <tex>deg^{out}(v) \geqslant \delta</tex>. Если <tex>\delta \geqslant 2</tex>, то в графе <tex>G</tex> существует простой цикл <tex>C</tex> длины хотя бы <tex>\delta + 1</tex>.
|proof=
Рассмотрим путь максимальной длины <tex>P = v_0 v_1 \dots v_s</tex>. Из последней вершины <tex>v_s</tex> выходит хотя бы <tex>\delta - 1</tex> ребро в вершины, отличные от <tex>v_{s - 1}</tex>. Так как путь <tex>P</tex> максимальный, то продлить его нельзя, а значит, что из <tex>v_s</tex> выходят ребра только в вершины, содержащиеся в пути <tex>P</tex>. Пусть <tex>v_m \in P</tex> {{---}} вершина с наименьшим номером, в которую входит ребро из <tex>v_s</tex>. Тогда во множество <tex>\{v_m \dots v_{s - 1}\}</tex> входят не менее <tex>\delta</tex> ребер, выходящих из <tex>v_s</tex>. То есть в это множестве хотя бы <tex>\delta</tex> вершин. Значит, в цикле <tex>v_m \dots v_{s - 1} v_s</tex> не менее <tex>\delta + 1</tex> вершины.
}}

== Теорема Гуйя-Ури ==
{{Теорема
|author=Гуйя-Ури, Ghouila-Houri
|statement=
Если <tex>G</tex> {{---}} сильно связный ориентированный граф c <tex>n</tex> вершинами и для каждой <tex>v \in V(G)</tex> выполняется 
<tex>
\Bigg\{
\begin{matrix}
deg^{in}(v) \geqslant n/2 \\
deg^{out}(v) \geqslant n/2 \\

\end{matrix}
</tex>, 
тогда <tex>G</tex> {{---}} гамильтонов.
|proof=
Будем доказывать теорему от противного. Предположим, что это не так. Очевидно, что условие теоремы выполняется при <tex>n = 2</tex> и <tex>n = 3</tex>. Тогда существует орсвязный граф <tex>G</tex> с <tex>n \geqslant 4</tex>, который удовлетворяет условию и при этом не является гамильтоновым. Пусть <tex>C</tex> {{---}} максимальный цикл в <tex>G</tex> длины <tex>k</tex>. По лемме о длине цикла и по предположению о том, что граф не является гамильтоновым, получаем соотношение <tex>1 + n/2 \leqslant k < n</tex>. Теперь рассмотрим <tex>P = v_0 \dots v_l</tex> {{---}} путь максимальной длины <tex>l \geqslant 0</tex> в <tex>G</tex> такой, что никакая вершина этого пути не принадлежит циклу <tex>C</tex>. Тогда <tex>k + l + 1 \leqslant n</tex>. Следовательно, <tex>l \leqslant n - k - 1 \leqslant n - (1 + n/2) - 1 \leqslant n/2 - 2</tex>. Таким образом, <tex>l \leqslant n/2 - 2</tex>. Это значит, что в вершину <tex>v_0</tex> входят как минимум два ребра, выходящие из вершин, лежащих на <tex>C</tex>, а из вершины <tex>v_l</tex> выходят как минимум два ребра, которые входят в вершины, принадлежащие <tex>C</tex> (так как если бы эти вершины не лежали на данном цикле, путь <tex>P</tex> можно было бы продлить). 
Пусть <tex>A</tex> {{---}} множество вершин, принадлежащих <tex>C</tex>, ребра из которых приходят в вершину <tex>v_0</tex>, а <tex>a</tex> {{---}} их количество. Тогда <tex>a \geqslant 2</tex>. Для каждой такой вершины следующая за ней в цикле <tex>C</tex> <tex>l + 1</tex> вершина не содержит входящих ребер, начало которых принадлежит <tex>v_l</tex>, иначе граф <tex>G</tex> содержал бы цикл длины <tex>> k</tex>. Заметим, что среди вершин множества <tex>A</tex> должна существовать такая вершина <tex>y</tex>, что следующая за ней <tex>l + 1</tex> вершина в цикле <tex>C</tex> не является ни отцом <tex>v_0</tex>, ни сыном <tex>v_l</tex>. 
Рассмотрим оставшуюся <tex>a - 1</tex> вершину множества <tex>A</tex>, отличную от <tex>y</tex>. В следующую за каждой из них, очевидно, не может приходить ребро из <tex>v_l</tex>. Следовательно, как минимум <tex>(a - 1) + (l + 1) = a + l</tex> вершин <tex>C</tex> не являются сыновьями <tex>v_l</tex>, в противном случае, опять же, граф содержал бы цикл длины <tex>> k</tex>. 
Так как <tex>P</tex> {{---}} самый длинный путь в <tex>G</tex>, ни одна вершина которого не принадлежит <tex>C</tex>, каждая вершина, ребро из которой приходит в <tex>v_0</tex>, лежит либо на <tex>P</tex>, либо на <tex>C</tex>. Так как <tex>deg^{in}(v_0) \geqslant n/2</tex>, то <tex>a + l \geqslant n/2</tex>, следовательно <tex>deg^{out}(v_l) \leqslant (n - 1) - (a + l) \leqslant (n - 1) - n/2 = n/2 - 1</tex>. Получаем противоречие с условием. Таким образом, предположение неверно, а значит, теорема доказана.
}}

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

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

@@ Строка 19: / Строка 19: @@
 \Bigg\{
 \begin{matrix}
-     deg^{in}(v) \geqslant n/2 \\
+     \deg^{in}(v) \geqslant n/2 \\
-     deg^{out}(v) \geqslant n/2 \\
+     \deg^{out}(v) \geqslant n/2 \\
 \end{matrix}

@@ Строка 26: / Строка 26: @@
 тогда <tex>G</tex> {{---}} гамильтонов.
 |proof=
-Будем доказывать теорему от противного. Предположим, что это не так. Очевидно, что условие теоремы выполняется при <tex>n = 2</tex> и <tex>n = 3</tex>. Тогда существует орсвязный граф <tex>G</tex> с <tex>n \geqslant 4</tex>, который удовлетворяет условию и при этом не является гамильтоновым. Пусть <tex>C</tex> {{---}} максимальный цикл в <tex>G</tex> длины <tex>k</tex>. По лемме о длине цикла и по предположению о том, что граф не является гамильтоновым, получаем соотношение <tex>1 + n/2 \leqslant k < n</tex>. Теперь рассмотрим <tex>P = v_0 \dots v_l</tex> {{---}} путь максимальной длины <tex>l \geqslant 0</tex> в <tex>G</tex> такой, что никакая вершина этого пути не принадлежит циклу <tex>C</tex>. Тогда <tex>k + l + 1 \leqslant n</tex>. Следовательно, <tex>l \leqslant n - k - 1 \leqslant n - (1 + n/2) - 1 \leqslant n/2 - 2</tex>. Таким образом, <tex>l \leqslant n/2 - 2</tex>. Это значит, что в вершину <tex>v_0</tex> входят как минимум два ребра, выходящие из вершин, лежащих на <tex>C</tex>, а из вершины <tex>v_l</tex> выходят как минимум два ребра, которые входят в вершины, принадлежащие <tex>C</tex> (так как если бы эти вершины не лежали на данном цикле, путь <tex>P</tex> можно было бы продлить). <br>
+Будем доказывать теорему от противного. Предположим, что это не так. Очевидно, что условие теоремы выполняется при <tex>n = 2</tex> и <tex>n = 3</tex>. Тогда существует орсвязный граф <tex>G</tex> с <tex>n \geqslant 4</tex>, который удовлетворяет условию и при этом не является гамильтоновым. Пусть <tex>C</tex> {{---}} максимальный цикл в <tex>G</tex> длины <tex>k</tex>. По лемме о длине цикла и по предположению о том, что граф не является гамильтоновым, получаем соотношение <tex>1 + n/2 \leqslant k < n</tex>. Теперь рассмотрим <tex>P = v_0 \dots v_l</tex> {{---}} путь максимальной длины <tex>l \geqslant 0</tex> в <tex>G</tex> такой, что никакая вершина этого пути не принадлежит циклу <tex>C</tex>. Тогда <tex>k + l + 1 \leqslant n</tex>. Следовательно, <tex>l \leqslant n - k - 1 \leqslant n - (1 + n/2) - 1 \leqslant n/2 - 2</tex>. Таким образом, <tex>l \leqslant n/2 - 2</tex>. Это значит, что в вершину <tex>v_0</tex> входят как минимум два ребра, выходящие из вершин, лежащих на <tex>C</tex>, а из вершины <tex>v_l</tex> выходят как минимум два ребра, которые входят в вершины, принадлежащие <tex>C</tex> (так как если бы эти вершины не лежали на данном цикле, путь <tex>P</tex> можно было бы продлить).
-Пусть <tex>A</tex> {{---}} множество вершин, принадлежащих <tex>C</tex>, ребра из которых приходят в вершину <tex>v_0</tex>, а <tex>a</tex> {{---}} их количество. Тогда <tex>a \geqslant 2</tex>. Для каждой такой вершины следующая за ней в цикле <tex>C</tex> <tex>l + 1</tex> вершина не содержит входящих ребер, начало которых принадлежит <tex>v_l</tex>, иначе граф <tex>G</tex> содержал бы цикл длины <tex>> k</tex>. Заметим, что среди вершин множества <tex>A</tex> должна существовать такая вершина <tex>y</tex>, что следующая за ней  <tex>l + 1</tex> вершина в цикле <tex>C</tex> не является ни отцом <tex>v_0</tex>, ни сыном <tex>v_l</tex>. <br>
-Рассмотрим оставшуюся <tex>a - 1</tex> вершину множества <tex>A</tex>, отличную от <tex>y</tex>. В следующую за каждой из них, очевидно, не может приходить ребро из <tex>v_l</tex>. Следовательно, как минимум <tex>(a - 1) + (l + 1) = a + l</tex> вершин <tex>C</tex> не являются сыновьями <tex>v_l</tex>, в противном случае, опять же, граф содержал бы цикл длины <tex>> k</tex>. <br>
+Пусть <tex>A</tex> {{---}} множество вершин, принадлежащих <tex>C</tex>, ребра из которых приходят в вершину <tex>v_0</tex>, а <tex>a</tex> {{---}} их количество. Тогда <tex>a \geqslant 2</tex>. Для каждой такой вершины следующая за ней в цикле <tex>C</tex> <tex>l + 1</tex> вершина не содержит входящих ребер, начало которых принадлежит <tex>v_l</tex>, иначе граф <tex>G</tex> содержал бы цикл длины <tex>> k</tex>. Заметим, что среди вершин множества <tex>A</tex> должна существовать такая вершина <tex>y</tex>, что следующая за ней  <tex>l + 1</tex> вершина в цикле <tex>C</tex> не является ни отцом <tex>v_0</tex>, ни сыном <tex>v_l</tex>.
 Так как <tex>P</tex> {{---}} самый длинный путь в <tex>G</tex>, ни одна вершина которого не принадлежит <tex>C</tex>, каждая вершина, ребро из которой приходит в <tex>v_0</tex>, лежит либо на <tex>P</tex>, либо на <tex>C</tex>. Так как <tex>deg^{in}(v_0) \geqslant n/2</tex>, то <tex>a + l \geqslant n/2</tex>, следовательно <tex>deg^{out}(v_l) \leqslant (n - 1) - (a + l) \leqslant (n - 1) - n/2 = n/2 - 1</tex>. Получаем противоречие с условием. Таким образом, предположение неверно, а значит, теорема доказана.
 }}

@@ Строка 6: / Строка 6: @@
 {{Лемма
 |about=о длине цикла в ориентированном графе
-|statement= Пусть <tex>G</tex> {{---}} произвольный ориентированный граф и для каждой вершины <tex>v \in V(G)</tex> выполняется <tex>deg^{out}(v) \geqslant \delta</tex>. Если <tex>\delta \geqslant 2</tex>, то в графе <tex>G</tex> существует простой цикл <tex>C</tex> длины хотя бы <tex>\delta + 1</tex>.
+|statement= Пусть <tex>G</tex> {{---}} произвольный ориентированный граф и для каждой вершины <tex>v \in V(G)</tex> выполняется <tex>\deg^{out}(v) \geqslant \delta</tex>. Если <tex>\delta \geqslant 2</tex>, то в графе <tex>G</tex> существует простой цикл <tex>C</tex> длины хотя бы <tex>\delta + 1</tex>.
 |proof=
 Рассмотрим путь максимальной длины <tex>P = v_0 v_1 \dots v_s</tex>. Из последней вершины <tex>v_s</tex> выходит хотя бы <tex>\delta - 1</tex> ребро в вершины, отличные от <tex>v_{s - 1}</tex>. Так как путь <tex>P</tex> максимальный, то продлить его нельзя, а значит, что из <tex>v_s</tex> выходят ребра только в вершины, содержащиеся в пути <tex>P</tex>. Пусть <tex>v_m \in P</tex> {{---}} вершина с наименьшим номером, в которую входит ребро из <tex>v_s</tex>. Тогда во множество <tex>\{v_m \dots v_{s - 1}\}</tex> входят не менее <tex>\delta</tex> ребер, выходящих из <tex>v_s</tex>. То есть в это множестве хотя бы <tex>\delta</tex> вершин. Значит, в цикле <tex>v_m \dots v_{s - 1} v_s</tex> не менее <tex>\delta + 1</tex> вершины.

@@ Строка 1: / Строка 1: @@
 {{Определение
 |definition=
 Ориентированный сильно связный граф называется '''орсвязаными'''.}}
 == Лемма о длине цикла в ориентированном графе ==
 {{Лемма
@@ Строка 32: / Строка 31: @@
 Так как <tex>P</tex> {{---}} самый длинный путь в <tex>G</tex>, ни одна вершина которого не принадлежит <tex>C</tex>, каждая вершина, ребро из которой приходит в <tex>v_0</tex>, лежит либо на <tex>P</tex>, либо на <tex>C</tex>. Так как <tex>deg^{in}(v_0) \geqslant n/2</tex>, то <tex>a + l \geqslant n/2</tex>, следовательно <tex>deg^{out}(v_l) \leqslant (n - 1) - (a + l) \leqslant (n - 1) - n/2 = n/2 - 1</tex>. Получаем противоречие с условием. Таким образом, предположение неверно, а значит, теорема доказана.
 }}