Изменения

Пусть :* <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| \geq geqslant 3 </tex> — количество вершин, * <tex> d_1 \leq leqslant d_2 \leq leqslant \ldots \leq leqslant d_n </tex> — его последовательность степеней. <br>Если Тогда если <tex> \forall k \in \mathbb N </tex> верна импликация: <br><center><tex> d_k \leq leqslant k < n/2 \rightarrow Rightarrow d_{n-k} \geq geqslant n-k, (*)</tex></center><br>то граф <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|гамильтонов]].

# {{Лемма|about=1

<tex>\ d_k \leq leqslant k \Leftrightarrow |\{ v \in |VG| : \mid d_v \leq leqslant k \}| \geq geqslant k. </tex>.

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

# {{Лемма|statement=Если <tex>\ d_{n-k} \ge n-k Leftarrow </tex>, то число вершин, степень которых не меньше <tex>\ n-k Из условия:* </tex>, больше или равно <tex>\ k+1 </tex>.Верно и обратное утверждение.|proof=Так как <tex>\ d_{n-k} \le d_{n-k+1} v \le .... \le d_n </tex> и <tex>in VG \ d_{n-k} mid d_v \ge n-leqslant k </tex>, то мы уже получаем <tex>\ d_{n-k}, d_{n-k+1}, ...., d_n | = k + 1 </tex> вершин, удовлетворяющих нашему требованию. Если степени некоторых вершин, предшествующих <tex>\ n-k </tex>, равны <tex>\ d_{n-k} p </tex>, то число вершин, удовлетворяющих требованию, превышает <tex>\ k+1 </tex>. <br>'''Доказательство в обратную сторону:''' <br>пусть у нас есть * <tex>p \ n </tex> вершин. Из них <tex>\ k+p </tex> <tex> (p > geqslant 0)</tex> имеют степень не меньше <tex>\ n-k </tex>. Расположим вершины в неубывающем порядке их степеней. Получим: <br><tex>d_1 \leqslant d_2 \ d_n leqslant \ge n-k, d_{n-1} ldots \leqslant d_k \leqslant \ge n-k, ..., d_{n-k} ldots \ge n-k, ... , leqslant d_{n-k-+ p+1} \ge n-k </tex>. Если <tex> p = 1 </tex>, то <tex> n-leqslant k-p+1 = n-k </tex>. Отсюда видно, что <tex>\ d_{n-k} Rightarrow d_k \ge n-leqslant k </tex>. }}

<tex>\ d_{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} \geqslant n - k </tex>,*) <tex> d_{n - k} \leqslant d_{n - k + 1} \leqslant \ldots \leqslant d_n </tex> выполнено для последовательности , * <tex>|\ d_1{ d_{n - k}, d_2d_{n - k + 1}, ... \ldots , d_n \}| = k + 1 </tex>. # <tex>\ d_1 { d_{n - k}, d_{n - k + 1}, \le d_1' , ... ldots , d_n \le 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 </tex>.Тогда <tex>\ (*) Leftarrow </tex> выполнено и для :* <tex>|\{ v \in VG \mid d_v \geqslant n - k \ d_1'}| = k + 1 + p, (p \geqslant 0)</tex>, Расположим вершины в неубывающем порядке их степеней... , <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 </tex>, то оно верно она верна и для неубывающей последовательности <tex> d' </tex>, мажорирующей её <tex> d </tex>.|proof=# Если <tex> d'_k > k </tex>, то первый аргумент импликации всегда ложен, следовательно импликация верна вне зависимости от второго аргумента. Значит, в этом случае импликация <tex> (*) </tex> верна для последовательности <tex> d' </tex>.# Если <tex> d'_k \leqslant k, \mbox{ } d'_{n - k} \geqslant d_{n - k} \geqslant n - k </tex>, то оба аргумента импликации всегда истинны. Значит, и в этом случае импликация <tex> (*) </tex> верна для последовательности<tex> d' </tex>.Значит, импликация <tex> (*) </tex> выполняется и для последовательности <tex> d' </tex>.

 Приведем доказательство от противного. Пусть существует граф с числом вершин <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|about=330px|thumb|center|Множество <tex> S </tex> обозначено красным цветом, множество <tex> T </tex> обозначено синим цветом]] Хватал{{Утверждение

Пусть <tex> G </tex> — [[Отношение связности, компоненты связности|связный граф]], количество вершин которого не меньше 3. Упорядочим степени вершин <tex>\ G </tex> по неубыванию.Если <tex>\forall k</tex> верно <tex> (*) </tex>: <tex>(d_k S \le k < n/2 cap T = \Rightarrow d_{n-k} \ge n-k) </tex>, то <tex> G emptyset </tex> — [[Гамильтоновы графы|гамильтонов]].

Приведем доказательство от противного.Пусть теорема Хватала не верна, то есть существует граф с числом вершин <tex>\ n \ge 3 </tex>, удовлетворяющий <tex>\ (*) </tex>, но негамильтонов.Будем добавлять в него [[Основные определения теории графов|рёбра]] до тех пор, пока не получим максимально возможный негамильтонов граф <tex> G </tex> (то есть добавление еще одного ребра сделает граф <tex> G </tex> гамильтоновым). Важно тоПредположим, что добавление рёбер не нарушает <tex>j \ (*) </tex>.Очевидно, что граф <tex>in S \ K_n </tex> гамильтонов для <tex>\ k \ge 3 cap T </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 \le \deg v </tex>.Добавив к <tex> G </tex> новое ребро <tex> e = uv </tex>, Тогда получим гамильтонов граф <tex> G + e</tex>.Рассмотрим [[Гамильтоновы графы|гамильтонов цикл]] графа <tex> G + e</tex>: в нём обязательно присутствует ребро <tex> e </tex>. <br>Отбрасывая ребро <tex> e </tex>, получим гамильтонову (<tex>u</tex>, <tex>v</tex>)-цепь в графе <tex> G </tex>: <tex> u = u_1 - u_2 - ... - u_n = v </tex>. <br>Пусть <tex>\ S = \xrightarrow{i|e_i = u_1 e_j} u_{ij +1} \in E(G)rightarrow \} </tex>. <br>Пусть <tex>ldots \ T = rightarrow u_n \xrightarrow{i|f_i = u_i u_n \in E(G)f_j} u_j \rightarrow u_{j - 1} </tex>. <br> <tex>\ S rightarrow \cap T = ldots \varnothing rightarrow u_1 </tex>, иначе в графе <tex> G </tex> есть гамильтонов циклчто противоречит условию, что граф негамильтонов.[[Файл: пусть z Hvatal_4.png|270px|thumb|center|]]Значит, <tex> \in S \cap T </tex>. Тогда получим гамильтонов цикл графа <tex> G </tex>: <tex>\ u_1 - u_{z+1} - u_{z+2} - ... - u_n - u_z - u_{z-1} - ... - u_1 </tex>. Из определений <tex>\ S </tex> и <tex>\ T </tex> следует, что <tex>\ S \cup T \subseteq \{1, 2, ..., n - 1 \} </tex>, поэтому <tex> \Rightarrow 2\deg u \le leqslant \deg u + \deg v = |S| + |T| = |S \cup T| < n </tex>. Значит, то есть <tex>\deg u < n/2 </tex>. <br> Так как <tex>\ S \cap T = \varnothing emptyset </tex>, ни одна вершина <tex>\ u_j </tex> не смежна с <tex>\ v = u_n </tex> (для <tex>\ j \in S </tex>). В силу выбора <tex> u </tex> и <tex> v </tex>, получим, что <tex>\deg u_j \le leqslant \deg u </tex>. Положим, что Пусть <tex>\ k = \deg u = |S| </tex>.Тогда имеется по крайней мере Значит, <tex>\ |S| = \deg u = exists k </tex> вершин, степень которых не превосходит <tex> k. <br/tex>. В силу первой леммы, выполняетсяПо лемме №1: <tex>\ d_k \le leqslant k < n/2 </tex>. <br>Исходя из В силу импликации <tex>\ (*) </tex>, получаем: <tex>\ d_{n-k} \ge geqslant n-k </tex>. <br>В силу второй леммыПо лемме №2, имеется по крайней мере <tex>\ exists k+1 </tex> вершин, степень которых не меньше <tex>\ n-k </tex>. <br> Так как <tex>\ k = \deg u </tex>, то вершина <tex>\ u </tex> может быть смежна максимум с <tex>\ k </tex> из этих <tex>\ k+1 </tex> вершин. Значит, существует вершина <tex>\ w </tex>, не являющаяся смежной с <tex>\ u </tex> и для которой <tex>\deg w \ge geqslant n-k </tex>. Тогда получим, что <tex>\deg u + \deg w \ge geqslant k + (n - k) = n > \deg u + \deg v </tex>, но это что противоречит выбору <tex>\ u </tex> и <tex>\ v </tex>. <br>  Значит, предположение неверно.

==ЛитератураСм. также==* [[Гамильтоновы графы]]* [[Теорема Дирака]]* [[Теорема Оре]] == Источники информации ==* Асанов М,., Баранский В., Расин В. — : ''Дискретная математика — : Графы, матроиды, алгоритмы''