В графе [math]\ G [/math], состоящем из [math]\ n [/math] вершин, [math]\ d_i [/math] - степень [math]\ i [/math] - ой вершины.
Все [math]\ d_i [/math] расположены в порядке неубывания.
[math]\ (*): [/math] [math]\forall k[/math] верна импликация [math](d_k \le k \lt n/2 \Rightarrow d_{n-k} \ge n-k)[/math]
| Лемма (I): |
Если [math]\ d_k \le k [/math], то число вершин, степень которых не превосходит [math]\ k [/math], больше или равно [math]\ k [/math].
Верно и обратное утверждение. |
| Доказательство: |
| [math]\triangleright[/math] |
|
Т.к. [math]\ d_1 \le d_2 \le ... \le d_k [/math], то уже есть [math]\ k [/math] вершин, степень которых не превосходит [math]\ k [/math]. Если степени некоторых вершин, следующих за [math]\ k [/math] равны [math]\ d_k [/math], то число вершин, удовлетворяющих требованию, превышает [math]\ k [/math].
Доказательство в обратную сторону:
Пусть у нас есть [math]\ n [/math] вершин. Из них [math]\ k + p (p \ge 0) [/math] вершин имеют степень не больше [math]\ k [/math].
Расположим вершины в неубывающем порядке их степеней. [math]\ d_1 \le k, d_2 \le k, ... , d_k \le k, ..., d_{k+p} \le k [/math]. Значит [math]\ d_k \le k [/math]. |
| [math]\triangleleft[/math] |
| Лемма (II): |
Если [math]\ d_{n-k} \ge n-k [/math], то число вершин, степень которых не меньше [math]\ n-k [/math], больше или равно [math]\ k+1 [/math].
Верно и обратное утверждение. |
| Доказательство: |
| [math]\triangleright[/math] |
|
Т.к. [math]\ d_{n-k} \le d_{n-k+1} \le .... \le d_n [/math] и [math]\ d_{n-k} \ge n-k [/math], то мы уже получаем [math]\ d_{n-k}, d_{n-k+1}, ...., d_n = k + 1 [/math] вершину, удовлетворяющую нашему требованию. Если степени некоторых вершин, предшествующих [math]\ n-k [/math] равны [math]\ d_{n-k} [/math], то число вершин, подходящих нашему требованию, превышает [math]\ k+1 [/math]
Доказательство в обратную сторону:
Пусть у нас есть [math]\ n [/math] вершин. Из них [math]\ k+p (p \gt 0)[/math] вершин имеют степень не меньше [math]\ n-k [/math]. Расположим вершины в неубывающем порядке их степеней. Получим : [math]\ d_n \ge n-k, d_{n-1} \ge n-k, ..., d_{n-k} \ge n-k, ... , d_{n-k-p+1} \ge n-k [/math]. Если p = 1, то n-k-p+1 = n-k. Отсюда видно, что [math]\ d_{n-k} \ge n-k [/math]. |
| [math]\triangleleft[/math] |
| Лемма (III): |
Пусть [math]\ (*) [/math] выполнена для последовательности [math]\ d_1, d_2, ... , d_n [/math].
Пусть [math]\ d_1 \le d_1' , ... , d_n \le d_n' [/math].
Тогда [math]\ (*) [/math] выполнена и для [math]\ d_1', ... , d_n' [/math]
Очевидно. |
| Лемма (IV): |
Если условие [math]\ (*) [/math] верно для некоторой последовательности степеней, то оно верно и для мажорирующей ее последовательности.
Очевидно. |
| Теорема (Хватала): |
Пусть G - связный граф, количество вершин которого не меньше 3. Упорядочим степени вершин G по неубыванию.
Если для [math]\forall k[/math] верна импликация [math](d_k \le k \lt n/2 \Rightarrow d_{n-k} \ge n-k) (*) [/math],
то G - гамильтонов. |
| Доказательство: |
| [math]\triangleright[/math] |
|
Приведем доказательство от противного.
Пусть теорема Хватала не верна, есть граф , где [math]\ n \ge 3 [/math], удовлетворяющий условию [math]\ (*) [/math], но не гамильтонов.
Будем добавлять в него ребра до тех пор, пока не получим максимально возможный негамильтонов граф G(т.е. добавление еще одного ребра сделает граф G гамильтоновым).
Добавление ребер не противоречит условию [math]\ (*) [/math].
Очевидно, что граф [math]\ K_n [/math] гамильтонов для [math]\ k \ge 3 [/math].
Будем считать G максимальным негамильтоновым остовным подграфом графа [math]\ K_n [/math].
Выберем две несмежные вершины U и V графа G с условием : [math]\ degU + degV [/math] - максимально.
Будем считать, [math]\ degU \le degV [/math].
Добавив к G новое ребро e = UV, получим гамильтонов граф G + UV.
Рассмотрим гамильтонов цикл графа G + UV : в нем обязательно присутствует ребро UV.
Отбрасывая ребро UV, получим гамильтонову (U, V)-цепь в графе G : [math]\ U = U_1 - U_2 - ... - U_n = V [/math].
Пусть [math]\ S = \{i|e_i = U_1 U_{i+1} \in E(G)\} [/math]
Пусть [math]\ T = \{i|f_i = U_i U_n \in E(G)\} [/math]
[math]\ S \cap T = \empty [/math], иначе в графе G есть гамильтонов цикл. Пусть j [math] \in S \cap T [/math]. Тогда получим гамильтонов цикл графа G : [math]\ U_1 - U_{j+1} - U_{j+2} - ... - U_n - U_j - U_{j-1} - ... - U_1 [/math]
Из определений [math]\ S [/math] и [math]\ T [/math] следует, что [math]\ S \cup T \subseteq \{1, 2, ..., n - 1 \} [/math] , поэтому [math]\ 2degU \le degU + degV = |S| + |T| = |S \cup T| \lt n [/math], т.е. [math]\ degU \lt n/2 [/math]
Т.к. [math]\ S \cap T = \empty [/math], ни одна вершина [math]\ U_j [/math] не смежна с [math]\ V = U_n [/math] (для [math]\ j
\in S [/math]). Отсюда в силу выбора [math]\ U [/math] и [math]\ V [/math] имеем [math]\ degU_j \le degU [/math]. Положим [math]\ k = degU [/math].
Тогда имеется по крайней мере [math]\ |S| = degU = k [/math] вершин, степень которых не превосходит k.
В силу леммы(I) выполняется : [math]\ d_k \le k \lt n/2 [/math]
По условию [math]\ (*) [/math] получаем : [math]\ d_{n-k} \ge n-k [/math]
В силу леммы(II) имеется по крайней мере [math]\ k+1 [/math] вершин, степень которых не меньше [math]\ n-k [/math]
Так как [math]\ k = degU [/math], то вершина [math]\ U [/math] может быть смежна, самое большее, с [math]\ k [/math] из этих [math]\ k+1 [/math] вершин. Значит существует вершина [math]\ W [/math], несмежная с [math]\ U [/math], и для которой [math]\ degW \ge n-k [/math]. Но тогда получим [math]\ degU + degW \ge k + (n - k) = n \gt degU + degV [/math], что противоречит выбору [math]\ U [/math] и [math]\ V [/math].
|
| [math]\triangleleft[/math] |
Литература
- Асанов М,, Баранский В., Расин В. - Дискретная математика - Графы, матроиды, алгоритмы
