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

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

Версия 08:21, 15 октября 2010

Все [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]