Теорема Гуйя-Ури — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Новая страница: «= Теорема Гуйя-Ури = {{Определение |definition= Ориентированный сильно связный граф называется...»)
 
м (rollbackEdits.php mass rollback)
 
(не показано 5 промежуточных версий 3 участников)
Строка 1: Строка 1:
= Теорема Гуйя-Ури =
 
 
 
{{Определение
 
{{Определение
 
|definition=
 
|definition=
 
Ориентированный сильно связный граф называется '''орсвязаными'''.}}
 
Ориентированный сильно связный граф называется '''орсвязаными'''.}}
 +
 
== Лемма о длине цикла в ориентированном графе ==
 
== Лемма о длине цикла в ориентированном графе ==
 
{{Лемма
 
{{Лемма
 
|about=о длине цикла в ориентированном графе
 
|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=
 
|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> вершины.
 
Рассмотрим путь максимальной длины <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> вершины.
Строка 20: Строка 19:
 
\Bigg\{
 
\Bigg\{
 
\begin{matrix}
 
\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}   
 
\end{matrix}   
Строка 27: Строка 26:
 
тогда <tex>G</tex> {{---}} гамильтонов.
 
тогда <tex>G</tex> {{---}} гамильтонов.
 
|proof=
 
|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>. Получаем противоречие с условием. Таким образом, предположение неверно, а значит, теорема доказана.
+
 
 +
Рассмотрим оставшуюся <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>. Получаем противоречие с условием. Таким образом, предположение неверно, а значит, теорема доказана.
 
}}
 
}}
 +
 +
== См. также ==
 +
* [[Теорема Дирака]]
 +
 +
== Источники информации ==
 +
* Gary Chartrand, Linda Lesniak, Ping Zhang (2010). ''Graphs & Digraphs, Fifth Edition'', chapter 4. ISBN 9781439895184.
 +
* Д. В. Карпов. ''Теория графов''.
 +
 +
[[Категория: Алгоритмы и структуры данных]]
 +
[[Категория: Обходы графов]]
 +
[[Категория: Гамильтоновы графы]]

Текущая версия на 19:34, 4 сентября 2022

Определение:
Ориентированный сильно связный граф называется орсвязаными.


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

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

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

Теорема (Гуйя-Ури, Ghouila-Houri):
Если [math]G[/math] — сильно связный ориентированный граф c [math]n[/math] вершинами и для каждой [math]v \in V(G)[/math] выполняется

[math] \Bigg\{ \begin{matrix} \deg^{in}(v) \geqslant n/2 \\ \deg^{out}(v) \geqslant n/2 \\ \end{matrix} [/math],

тогда [math]G[/math] — гамильтонов.
Доказательство:
[math]\triangleright[/math]

Будем доказывать теорему от противного. Предположим, что это не так. Очевидно, что условие теоремы выполняется при [math]n = 2[/math] и [math]n = 3[/math]. Тогда существует орсвязный граф [math]G[/math] с [math]n \geqslant 4[/math], который удовлетворяет условию и при этом не является гамильтоновым. Пусть [math]C[/math] — максимальный цикл в [math]G[/math] длины [math]k[/math]. По лемме о длине цикла и по предположению о том, что граф не является гамильтоновым, получаем соотношение [math]1 + n/2 \leqslant k \lt n[/math]. Теперь рассмотрим [math]P = v_0 \dots v_l[/math] — путь максимальной длины [math]l \geqslant 0[/math] в [math]G[/math] такой, что никакая вершина этого пути не принадлежит циклу [math]C[/math]. Тогда [math]k + l + 1 \leqslant n[/math]. Следовательно, [math]l \leqslant n - k - 1 \leqslant n - (1 + n/2) - 1 \leqslant n/2 - 2[/math]. Таким образом, [math]l \leqslant n/2 - 2[/math]. Это значит, что в вершину [math]v_0[/math] входят как минимум два ребра, выходящие из вершин, лежащих на [math]C[/math], а из вершины [math]v_l[/math] выходят как минимум два ребра, которые входят в вершины, принадлежащие [math]C[/math] (так как если бы эти вершины не лежали на данном цикле, путь [math]P[/math] можно было бы продлить).

Пусть [math]A[/math] — множество вершин, принадлежащих [math]C[/math], ребра из которых приходят в вершину [math]v_0[/math], а [math]a[/math] — их количество. Тогда [math]a \geqslant 2[/math]. Для каждой такой вершины следующая за ней в цикле [math]C[/math] [math]l + 1[/math] вершина не содержит входящих ребер, начало которых принадлежит [math]v_l[/math], иначе граф [math]G[/math] содержал бы цикл длины [math]\gt k[/math]. Заметим, что среди вершин множества [math]A[/math] должна существовать такая вершина [math]y[/math], что следующая за ней [math]l + 1[/math] вершина в цикле [math]C[/math] не является ни отцом [math]v_0[/math], ни сыном [math]v_l[/math].

Рассмотрим оставшуюся [math]a - 1[/math] вершину множества [math]A[/math], отличную от [math]y[/math]. В следующую за каждой из них, очевидно, не может приходить ребро из [math]v_l[/math]. Следовательно, как минимум [math](a - 1) + (l + 1) = a + l[/math] вершин [math]C[/math] не являются сыновьями [math]v_l[/math], в противном случае, опять же, граф содержал бы цикл длины [math]\gt k[/math].

Так как [math]P[/math] — самый длинный путь в [math]G[/math], ни одна вершина которого не принадлежит [math]C[/math], каждая вершина, ребро из которой приходит в [math]v_0[/math], лежит либо на [math]P[/math], либо на [math]C[/math]. Так как [math]\deg^{in}(v_0) \geqslant n/2[/math], то [math]a + l \geqslant n/2[/math], следовательно [math]\deg^{out}(v_l) \leqslant (n - 1) - (a + l) \leqslant (n - 1) - n/2 = n/2 - 1[/math]. Получаем противоречие с условием. Таким образом, предположение неверно, а значит, теорема доказана.
[math]\triangleleft[/math]

См. также

Источники информации

  • Gary Chartrand, Linda Lesniak, Ping Zhang (2010). Graphs & Digraphs, Fifth Edition, chapter 4. ISBN 9781439895184.
  • Д. В. Карпов. Теория графов.