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