Теорема Хватала — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 49: Строка 49:
 
Выберем две несмежные вершины U и V графа '''G''' с условием : <math>\ degU + degV </math> - максимально.
 
Выберем две несмежные вершины U и V графа '''G''' с условием : <math>\ degU + degV </math> - максимально.
 
Будем считать, <math>\ degU \le degV </math>.
 
Будем считать, <math>\ degU \le degV </math>.
 
+
Добавив к '''G''' новое ребро <math>\ e = UV </math>, получим гамильтонов граф '''G''' + UV.
 +
Рассмотрим гамильтонов цикл графа '''G''' + UV : в нем обязательно присутствует ребро UV. Отбрасывая ребро UV, получим гамильтонову цепь (U, V) в графе '''G''' : <math>\ U = U_1 - U_2 - ... - U_n = V </math>.
 
}}
 
}}

Версия 05:11, 13 октября 2010

Теорема (Хватала):
Пусть G - связный граф, количество вершин которого не меньше 3. Упорядочим степени вершин G по неубыванию.

Если для [math]\forall k[/math] верна импликация [math]d_k \le k \lt n/2 \Rightarrow d_{n-k} \ge n-k (*) [/math],

то G - гамильтонов.

Прежде чем доказать теорему, добавим несколько лемм.

Лемма (I):
Если [math]\ d_k \le k [/math], то число вершин, степень которых не превосходит [math]\ k [/math], больше или равно [math]\ k [/math]. Верно и обратное утверждение.
Лемма (II):
Если [math]\ d_n-k \ge n-k [/math], то число вершин, степень которых не меньше [math]\ n-k [/math], больше или равно [math]\ k+1 [/math]. Верно и обратное утверждение.
Лемма (III):
Пусть (*) выполнена для последовательности [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]
Теорема (Хватала):
Формулировка приведена выше.
Доказательство:
[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 новое ребро [math]\ e = UV [/math], получим гамильтонов граф G + UV.

Рассмотрим гамильтонов цикл графа G + UV : в нем обязательно присутствует ребро UV. Отбрасывая ребро UV, получим гамильтонову цепь (U, V) в графе G : [math]\ U = U_1 - U_2 - ... - U_n = V [/math].
[math]\triangleleft[/math]