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

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

Определение:

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

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

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

Пусть [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]