Изменения

{{ТеоремаОпределение|definition=Пусть [[Основные_определения_теории_графов#.D0.9D.D0.B5.D0.BE.D1.80.D0.B8.D0.B5.D0.BD.D1.82.D0.B8.D1.80.D0.BE.D0.B2.D0.B0.D0.BD.D0.BD.D1.8B.D0.B5_.D0.B3.D1.80.D0.B0.D1.84.D1.8B|неориентированный граф]] <tex> G </tex> имеет <tex> n </tex> вершин: <tex> v_1, v_2, \ldots, v_n </tex>. Пусть <tex> d_i = \deg v_i \mbox{ } (i = \overline{1, n}) </tex> и вершины графа упорядочены таким образом, что <tex> d_1 \leqslant d_2 \leqslant \ldots \leqslant d_n </tex>. Последовательность <tex> d_1, d_2, \ldots, d_n </tex> называют '''последовательностью степеней''' графа <tex> G </tex>.}} {{Лемма

Пусть неориентированный граф <tex> G'''</tex> получен из неориентированного графа <tex> G </tex> добавлением одного нового ребра <tex> e </tex>. Тогда последовательность степеней графа <tex> G </tex> мажорируется последовательностью степеней графа <tex> G''' - связный граф, количество вершин которого не меньше 3</tex>. Упорядочим степени вершин |proof=''Замечание'G''' по неубыванию: Если в неубывающей последовательности <tex> d_1, d_2, \ldots, d_n </tex> увеличить на единицу число <tex> d_i </tex>, а затем привести последовательность к неубывающему виду, переставив число <tex> d_i + 1 </tex> на положенное место <tex> j </tex>, то исходная последовательность будет мажорироваться полученной.Если для <mathtex>j = i</tex>, то утверждение леммы, очевидно, выполняется. Пусть <tex>j \forall kneq i</mathtex> верна импликация .[[Файл: Hvatal_1.png|270px|thumb|center|Исходная последовательность степеней <tex> d </tex>]] * Рассмотрим элементы с номерами <mathtex>d_k s = \le k overline{1, i - 1} </tex>. Они не изменились, следовательно мажорируются собой.* Рассмотрим элементы с номерами <tex> s = \overline{i, j - 1} </tex>. <tex> s </tex>-й элемент полученной последовательности равен <tex> s + 1 < n/2 tex>-му элементу исходной. <tex> d_s \leqslant d_{s + 1} \Rightarrow d_s \leqslant d'_s = d_{ns + 1} </tex>.* Расмотрим <tex>j</tex>-ый элемент. Имеем <tex>d'_j \ge d'_{j-k1} = d_{j} </tex>.* Рассмотрим элементы с номерами <tex> s = \ge overline{j + 1, n-k } </tex>. Они не изменились, следовательно мажорируются собой.[[Файл: Hvatal_2.png|290px|thumb|center|Новая последовательность степеней <tex> d' </tex>]]При добавлении в граф ребра <tex> e = uv, \mbox{ } (*u \neq v) </mathtex>, степени вершин <tex> u </tex> и <tex> v </tex>увеличатся на единицу. Для доказательства леммы,дважды воспользуемся замечанием.то '''G''' - гамильтоновЗначит, последовательность степеней полученного графа мажорирует последовательность степеней исходного.

Прежде чем доказать теорему{{Теорема|about=Хватал|statement=Пусть:* <tex> G </tex> — [[Отношение_связности, добавим несколько лемм_компоненты_связности#.D0.A1.D0.BB.D1.83.D1.87.D0.B0.D0.B9_.D0.BD.D0.B5.D0.BE.D1.80.D0.B8.D0.B5.D0.BD.D1.82.D0.B8.D1.80.D0.BE.D0.B2.D0.B0.D0.BD.D0.BD.D0.BE.D0.B3.D0.BE_.D0.B3.D1.80.D0.B0.D1.84.D0.B0|связный граф]],* <tex> n = |VG| \geqslant 3 </tex> — количество вершин,* <tex> d_1 \leqslant d_2 \leqslant \ldots \leqslant d_n </tex> — его последовательность степеней.Тогда если <tex> \forall k \in \mathbb N </tex> верна импликация: <br><center><tex> d_k \leqslant k < n/2 \Rightarrow d_{n - k} \geqslant n - k, (*) </tex></center>то граф <tex> G </tex> [[Гамильтоновы_графы#.D0.9E.D1.81.D0.BD.D0.BE.D0.B2.D0.BD.D1.8B.D0.B5_.D0.BE.D0.BF.D1.80.D0.B5.D0.B4.D0.B5.D0.BB.D0.B5.D0.BD.D0.B8.D1.8F|гамильтонов]].|proof=Для доказательства теоремы, докажем 3 леммы.

Если <mathtex>d_k \leqslant k \Leftrightarrow |\{ v \in VG \mid d_v \leqslant k \}| \ geqslant k. </tex>|proof=<tex> \Rightarrow </tex> Пусть:* <tex> d_1 \leqslant d_2 \leqslant \ldots \leqslant d_k </tex>,* <tex> d_k \leqslant k </tex>,* <tex> |\{ d_1, d_2, \ldots, d_k \le }| = k </mathtex>.<tex> \{ d_1, то число вершинd_2, степень которых не превосходит \ldots, d_k \} \subseteq \{ v \in VG \mid d_v \leqslant k \} \Rightarrow |\{ v \in VG \mid d_v \leqslant k \}| \geqslant k </tex>. <mathtex>\ Leftarrow </tex> Из условия:* <tex> |\{ v \in VG \mid d_v \leqslant k \}| = k + p </mathtex>, больше или равно * <mathtex>p \ k geqslant 0 </mathtex>. Верно и обратное утверждениеРасположим вершины в неубывающем порядке их степеней. <br><tex> d_1 \leqslant d_2 \leqslant \ldots \leqslant d_k \leqslant \ldots \leqslant d_{k + p} \leqslant k \Rightarrow d_k \leqslant k </tex>.

Если <mathtex>\ d_nd_{n - k} \geqslant n - k \Leftrightarrow |\{ v \in VG \mid d_v \geqslant n - k \}| \geqslant k + 1. </tex>|proof=<tex> \Rightarrow </tex> Пусть:* <tex> d_{n -k } \ge geqslant n-k </mathtex>, то число вершин* <tex> d_{n - k} \leqslant d_{n - k + 1} \leqslant \ldots \leqslant d_n </tex>, степень которых не меньше * <mathtex>|\ { d_{n - k}, d_{n-k + 1}, \ldots , d_n \}| = k + 1 </mathtex>.<tex> \{ d_{n - k}, d_{n - k + 1}, \ldots , больше или равно d_n \} \subseteq \{ v \in VG \mid d_v \geqslant n - k \} \Rightarrow \{ v \in VG \mid d_v \geqslant n - k \} \geqslant k + 1 <math/tex>. <tex>\ Leftarrow </tex>:* <tex> |\{ v \in VG \mid d_v \geqslant n - k \}| = k+1 + p, (p \geqslant 0)</mathtex>,Расположим вершины в неубывающем порядке их степеней.Верно и обратное утверждение<tex> d_n \geqslant d_{n - 1} \ldots \geqslant d_{n - k} \geqslant \ldots \geqslant d_{n - k - p} \geqslant n - k \Rightarrow d_{n - k} \geqslant n - k </tex>.

Пусть '''Если импликация <tex> (*)''' выполнена </tex> верна для некоторой последовательности степеней <tex> d <math/tex>\ d_1, d_2то она верна и для неубывающей последовательности <tex> d' </tex>, мажорирующей <tex> d </tex>.|proof=# Если <tex> d'_k > k </tex>, то первый аргумент импликации всегда ложен, следовательно импликация верна вне зависимости от второго аргумента.. Значит, d_n в этом случае импликация <tex> (*) </mathtex> верна для последовательности <tex> d' </tex>. Пусть # Если <mathtex>d'_k \ d_1 leqslant k, \le d_1mbox{ } d' _{n - k} \geqslant d_{n - k} \geqslant n - k </tex>, то оба аргумента импликации всегда истинны... Значит, d_n \le d_nи в этом случае импликация <tex> (*) </tex> верна для последовательности <tex> d' </mathtex>.Тогда Значит, импликация <mathtex>\ (*) </mathtex> выполнена выполняется и для последовательности <mathtex>\ d_1', ... , d_nd' </mathtex>.

Приведем доказательство от противного. Пусть существует граф с числом вершин <tex> n \geqslant 3 </tex>, удовлетворяющий <tex> (*) </tex>, но негамильтонов.Будем добавлять в него ребра до тех пор, пока не получим максимально возможный негамильтонов граф <tex> G </tex> (то есть добавление еще одного ребра сделает граф <tex> G </tex> гамильтоновым). По лемме о добавлении ребра и лемме №3 импликация <tex> (*) </tex> остается верной для графа <tex> G </tex>.Очевидно, что граф <tex>\ K_n </tex> гамильтонов при <tex> k \geqslant 3 </tex>.Будем считать <tex> G </tex> максимальным негамильтоновым остовным подграфом графа <tex> K_n </tex>. Выберем две несмежные вершины <tex> u </tex> и <tex> v </tex> графа <tex> G </tex>, такие что <tex> \deg u + \deg v </tex> — максимально.Будем считать, что <tex> \deg u \leqslant \deg v </tex>.Добавив к <tex> G </tex> новое ребро <tex> e = uv </tex>, получим гамильтонов граф <tex> G + e </tex>.Рассмотрим гамильтонов цикл графа <tex> G + e </tex>: в нём обязательно присутствует ребро <tex> e </tex>.Отбрасывая ребро <tex> e </tex>, получим гамильтонову <tex> (u, v) </tex>-цепь в графе <tex> G </tex>: <tex> u = u_1 \rightarrow u_2 \rightarrow \ldots \rightarrow u_n = v </tex>. Пусть <tex> S = \{i \mid e_i = u_1 u_{Теоремаi + 1} \in EG\}, T = \{ i \mid f_i = u_i u_n \in EG\} </tex>.[[Файл: Hvatal_3.png|330px|thumb|center|about=Множество <tex> S </tex> обозначено красным цветом, множество <tex> T </tex> обозначено синим цветом]] Хватала{{Утверждение

Формулировка приведена выше<tex> S \cap T = \emptyset </tex>.

Приведем доказательство от противногоПредположим, что <tex> j \in S \cap T </tex>.Пусть есть граф , где Тогда получим гамильтонов цикл графа <tex> G </tex>: <mathtex>u_1 \xrightarrow{e_j} u_{j + 1} \rightarrow \ldots \rightarrow u_n \xrightarrow{f_j} u_j \rightarrow u_{j - 1} \ n rightarrow \ldots \ge 3 rightarrow u_1 </mathtex>, удовлетворяющий что противоречит условию , что граф негамильтонов.[[Файл: Hvatal_4.png|270px|thumb|center|]]Значит, <mathtex>S \ (*) cap T </mathtex>, но не гамильтонов.Будем добавлять в него ребра до тех пор}} Из определений <tex> S </tex> и <tex> T </tex> следует, что <tex> S \cup T \subseteq \{1, 2, пока не получим максимально возможный негамильтонов граф '''G'''(т.е. добавление еще одного ребра сделает граф '''G''' гамильтоновым). , n - 1 \} \Rightarrow 2 \deg u \leqslant \deg u + \deg v = |S| + |T| = |S \cup T| < n </tex>. Значит, <tex> \deg u < n/2 </tex>. Добавление ребер Так как <tex> S \cap T = \emptyset </tex>, ни одна вершина <tex> u_j </tex> не противоречит условию смежна с <tex> v = u_n </tex> (для <mathtex>j \ (*in S </tex>) . В силу выбора <tex> u </tex> и <tex> v </mathtex>.Очевидно, получим, что граф <mathtex>\ K_n deg u_j \leqslant \deg u </mathtex> гамильтонов для . Пусть <mathtex>\ k = \ge 3 deg u = |S| </mathtex>.Будем считать '''G''' максимальным негамильтоновым подграфом графа Значит, <mathtex>\ K_n exists k </mathtex> вершин, степень которых не превосходит <tex> k </tex>.Выберем две несмежные вершины U и V графа '''G''' с условием По лемме №1: <mathtex>d_k \ degU + degV leqslant k < n/2 </tex>. В силу импликации <tex> (*) </mathtex>: <tex> d_{n - k} \geqslant n - максимальноk </tex>.Будем считатьПо лемме №2, <mathtex>\ degU \le degV exists k + 1 </tex> вершин, степень которых не меньше <tex> n - k </mathtex>.Добавив к '''G''' новое ребро Так как <mathtex>k = \ e = UV deg u </mathtex>, получим гамильтонов граф '''G''' то вершина <tex> u </tex> может быть смежна максимум с <tex> k </tex> из этих <tex> k+ UV1 </tex> вершин.Рассмотрим гамильтонов цикл графа '''G''' + UV : в нем обязательно присутствует ребро UV. Отбрасывая ребро UVЗначит, получим гамильтонову цепь (Uсуществует вершина <tex> w </tex>, V) в графе '''G''' : не являющаяся смежной с <tex> u </tex> и для которой <mathtex>\ U = U_1 - U_2 deg w \geqslant n - k </tex>... Тогда получим, что <tex> \deg u + \deg w \geqslant k + (n - U_n k) = V n > \deg u + \deg v </tex>, что противоречит выбору <tex> u </tex> и <tex> v </mathtex>. Значит, предположение неверно.