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

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 8: Строка 8:
 
}}
 
}}
  
Прежде чем доказать теорему, добавим несколько лемм.
+
Прежде, чем доказать теорему, добавим несколько лемм.
  
 
{{Лемма
 
{{Лемма
Строка 30: Строка 30:
 
III
 
III
 
|statement=
 
|statement=
Пусть '''(*)''' выполнена для последовательности <math>\ d_1, d_2, ... , d_n </math>.  
+
Пусть <math>\ (*) </math> выполнена для последовательности <math>\ d_1, d_2, ... , d_n </math>.  
 
Пусть <math>\ d_1 \le d_1' , ... , d_n \le d_n' </math>.
 
Пусть <math>\ d_1 \le d_1' , ... , d_n \le d_n' </math>.
 
Тогда <math>\ (*) </math> выполнена и для <math>\ d_1', ... , d_n' </math>
 
Тогда <math>\ (*) </math> выполнена и для <math>\ d_1', ... , d_n' </math>
 +
}}
 +
{{Лемма
 +
|about=
 +
IV
 +
|statement=
 +
Если условие <math>\ (*) </math> верно для некоторой последовательности степеней, то оно верно и для мажорирующей ее последовательности
 
}}
 
}}
 
<br>
 
<br>
Строка 43: Строка 49:
 
|proof=
 
|proof=
 
Приведем доказательство от противного.
 
Приведем доказательство от противного.
Пусть есть граф , где <math>\ n \ge 3 </math>, удовлетворяющий условию <math>\ (*) </math>, но не гамильтонов.
+
Пусть теорема Хватала не верна, есть граф , где <math>\ n \ge 3 </math>, удовлетворяющий условию <math>\ (*) </math>, но не гамильтонов.
 
Будем добавлять в него ребра до тех пор, пока не получим максимально возможный негамильтонов граф '''G'''(т.е. добавление еще одного ребра сделает граф '''G''' гамильтоновым).  
 
Будем добавлять в него ребра до тех пор, пока не получим максимально возможный негамильтонов граф '''G'''(т.е. добавление еще одного ребра сделает граф '''G''' гамильтоновым).  
 
Добавление ребер не противоречит условию <math>\ (*) </math>.
 
Добавление ребер не противоречит условию <math>\ (*) </math>.
Строка 51: Строка 57:
 
Будем считать, <math>\ degU \le degV </math>.
 
Будем считать, <math>\ degU \le degV </math>.
 
Добавив к '''G''' новое ребро <math>\ e = UV </math>, получим гамильтонов граф '''G''' + UV.
 
Добавив к '''G''' новое ребро <math>\ e = UV </math>, получим гамильтонов граф '''G''' + UV.
Рассмотрим гамильтонов цикл графа '''G''' + UV : в нем обязательно присутствует ребро UV. Отбрасывая ребро UV, получим гамильтонову цепь (U, V) в графе '''G''' : <math>\ U = U_1 - U_2 - ... - U_n = V </math>. <br>
+
Рассмотрим гамильтонов цикл графа '''G''' + UV : в нем обязательно присутствует ребро UV. Отбрасывая ребро UV, получим гамильтонову (U, V)-цепь в графе '''G''' : <math>\ U = U_1 - U_2 - ... - U_n = V </math>. <br>
 
Пусть <math>\ S = \{i|e_i = U_1 U_{i+1} \in E(G)\} </math> <br>
 
Пусть <math>\ S = \{i|e_i = U_1 U_{i+1} \in E(G)\} </math> <br>
 
Пусть <math>\ T = \{i|f_i = U_i U_n \in E(G)\} </math> <br>  
 
Пусть <math>\ T = \{i|f_i = U_i U_n \in E(G)\} </math> <br>  
 
<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> <br>
 
<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> <br>
Из определений <math>\ S </math> и <math>\ T </math> следует, что <math>\ S \cup T \sube \{1, 2, ..., n - 1 \} </math> , поэтому <math>\ 2degU \le degU + degV = |S| + |T| < n </math>, т.е. <math>\ degU < n/2 </math> <br>
+
Из определений <math>\ S </math> и <math>\ T </math> следует, что <math>\ S \cup T \sube \{1, 2, ..., n - 1 \} </math> , поэтому <math>\ 2degU \le degU + degV = |S| + |T| = |S \cup T| < n </math>, т.е. <math>\ degU < n/2 </math> <br>
Т.к. <math>\ S \cap T  = \empty </math>, ни одна вершина <math>\ U_j </math> не смежна с <math>\ V = U_n </math> (<math> j  
+
Т.к. <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>
+
\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.
 
Тогда имеется по крайней мере <math>\ |S| = degU = k </math> вершин, степень которых не превосходит k.
 
В силу леммы(I) выполняется : <math>\ d_k \le k < n/2 </math> <br>
 
В силу леммы(I) выполняется : <math>\ d_k \le k < n/2 </math> <br>
 
По условию <math>\ (*) </math> получаем : <math>\ d_{n-k} \ge n-k </math> <br>
 
По условию <math>\ (*) </math> получаем : <math>\ d_{n-k} \ge n-k </math> <br>
В силу луммы(II) имеется по крайней мере <math>\ k+1 </math> вершин, степень которых не меньше <math>\ n-k </math> <br>
+
В силу леммы(II) имеется по крайней мере <math>\ k+1 </math> вершин, степень которых не меньше <math>\ n-k </math> <br>
Так как <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 > degU + degV </math>, что противоречит выбору <math>\ U </math> и <math>\ V </math>. <br>
+
Так как <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 > degU + degV </math>, что противоречит выбору <math>\ U </math> и <math>\ V </math>. <br>
 
}}
 
}}

Версия 06:29, 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]\ (*) [/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] верно для некоторой последовательности степеней, то оно верно и для мажорирующей ее последовательности


Теперь вернемся к доказательству теоремы.

Теорема (Хватала):
Формулировка приведена выше.
Доказательство:
[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]\ 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 \sube \{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]