Изменения
Нет описания правки
{{ТеоремаОпределение|aboutdefinition=ХваталаПусть [[Основные_определения_теории_графов#.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|statement=Пусть '''G''' - связный неориентированный граф, количество вершин которого не меньше 3. Упорядочим степени вершин ''']] <tex> G''' по неубыванию.Если для <math/tex> имеет <tex>\forall kn </mathtex> верна импликация вершин: <mathtex>(d_k v_1, v_2, \le k ldots, v_n < n/2 tex>. Пусть <tex> d_i = \deg v_i \Rightarrow d_mbox{n-k} (i = \ge overline{1, n-k}) (*) </mathtex> и вершины графа упорядочены таким образом, что <tex> d_1 \leqslant d_2 \leqslant \ldots \leqslant d_n </tex>. Последовательность <tex>d_1, d_2, \ldots,то d_n </tex> называют '''Gпоследовательностью степеней''' - гамильтоновграфа <tex> G </tex>.
}}
{{Лемма
|about=
|statement=
Пусть неориентированный граф <tex> G' </tex> получен из неориентированного графа <tex> G </tex> добавлением одного нового ребра <tex> e </tex>. Тогда последовательность степеней графа <tex> G </tex> мажорируется последовательностью степеней графа <tex> G' </tex>.|proof=''Замечание'': Если в неубывающей последовательности <mathtex>d_1, d_2, \ d_k \le k ldots, d_n </tex> увеличить на единицу число <tex> d_i </tex>, а затем привести последовательность к неубывающему виду, переставив число <tex> d_i + 1 </tex> на положенное место <tex> j </tex>, то исходная последовательность будет мажорироваться полученной. Если <tex>j = i</mathtex>, то число вершинутверждение леммы, очевидно, выполняется. Пусть <tex>j \neq i</tex>.[[Файл: Hvatal_1.png|270px|thumb|center|Исходная последовательность степеней <tex> d </tex>]] * Рассмотрим элементы с номерами <tex> s = \overline{1, степень которых i - 1} </tex>. Они не превосходит изменились, следовательно мажорируются собой.* Рассмотрим элементы с номерами <tex> s = \overline{i, j - 1} </tex>. <tex> s </tex>-й элемент полученной последовательности равен <tex> s + 1 </tex>-му элементу исходной. <tex> d_s \leqslant d_{s + 1} \Rightarrow d_s \leqslant d'_s = d_{s + 1} </tex>.* Расмотрим <tex>j</tex>-ый элемент. Имеем <mathtex>d'_j \ k ge d'_{j-1} = d_{j} </mathtex>.* Рассмотрим элементы с номерами <tex>s = \overline{j + 1, больше или равно n} </tex>. Они не изменились, следовательно мажорируются собой.[[Файл: Hvatal_2.png|290px|thumb|center|Новая последовательность степеней <tex> d' </tex>]]При добавлении в граф ребра <mathtex>e = uv, \mbox{ } (u \ k neq v) </mathtex>, степени вершин <tex> u </tex> и <tex> v </tex> увеличатся на единицу. Для доказательства леммы, дважды воспользуемся замечанием. Верно и обратное утверждениеЗначит, последовательность степеней полученного графа мажорирует последовательность степеней исходного.
}}
{{Теорема
|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 леммы.
{{Лемма
|about=
|statement=
}}
{{Лемма
|about=
|statement=
<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> Пусть :* <mathtex>d_{n - k} \ (geqslant n - k </tex>,*) <tex> d_{n - k} \leqslant d_{n - k + 1} \leqslant \ldots \leqslant d_n </mathtex> выполнена для последовательности , * <mathtex>|\ d_1{ d_{n - k}, d_2d_{n - k + 1}, ... \ldots , d_n \}| = k + 1 </mathtex>. Пусть <mathtex>\ 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 </mathtex>.Тогда <mathtex>\ (*) Leftarrow </mathtex> выполнена и для :* <mathtex>|\{ v \ d_1'in VG \mid d_v \geqslant n - k \}| = 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 </mathtex>.
}}
{{Лемма
|about=
|statement=
Если условие импликация <mathtex>\ (*) </mathtex> верно верна для некоторой последовательности степеней<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 <br/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> обозначено синим цветом]] Хватала{{Утверждение
|statement=
|proof=
}}
==См. также==
* [[Гамильтоновы графы]]
* [[Теорема Дирака]]
* [[Теорема Оре]]
== Источники информации ==
* Асанов М., Баранский В., Расин В.: ''Дискретная математика: Графы, матроиды, алгоритмы''
[[Категория: Алгоритмы и структуры данных]]
[[Категория: Обходы графов]]
[[Категория: Гамильтоновы графы]]