271
правка
Изменения
Нет описания правки
Все <tex>\ d_i </tex> расположены в порядке неубывания. <br>
<tex>\ (*): </tex> <tex>\forall k</tex> верна импликация <tex>(d_k \le k < n/2 \Rightarrow d_{n-k} \ge n-k)</tex> <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>
Пусть у нас есть <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>. Если <tex> p = 1</tex>, то <tex> n-k-p+1 = n-k</tex>. Отсюда видно, что <tex>\ d_{n-k} \ge n-k </tex>.
}}
<br>
Хватал
|statement=
Пусть '''<tex> G''' </tex> - [[Отношение связности, компоненты связности|связный граф]], количество вершин которого не меньше 3. Упорядочим степени вершин '''<tex>\ G''' </tex> по неубыванию.
Если для <tex>\forall k</tex> верна импликация <tex>(d_k \le k < n/2 \Rightarrow d_{n-k} \ge n-k) (*) </tex>,
то '''<tex> G''' </tex> - [[Гамильтоновы графы|гамильтонов]].
|proof=
Приведем доказательство от противного.
Пусть теорема Хватала не верна, есть граф, где <tex>\ n \ge 3 </tex>, удовлетворяющий условию <tex>\ (*) </tex>, но не гамильтонов.
Будем добавлять в него [[Основные определения теории графов|ребра]] до тех пор, пока не получим максимально возможный негамильтонов граф '''<tex> G'''</tex>(т.е. то есть добавление еще одного ребра сделает граф '''<tex> G''' </tex> гамильтоновым).
Добавление ребер не противоречит условию <tex>\ (*) </tex>.
Очевидно, что граф <tex>\ K_n </tex> гамильтонов для <tex>\ k \ge 3 </tex>.
Будем считать '''<tex> G''' </tex> максимальным негамильтоновым остовным подграфом графа <tex>\ K_n </tex>.Выберем две несмежные вершины U <tex> u </tex> и V <tex> v </tex> графа '''<tex> G''' </tex> с условием : <tex>\ degU deg u + degV \deg v </tex> - максимально.Будем считать, <tex>\ degU deg u \le degV \deg v </tex>.Добавив к '''<tex> G''' </tex> новое ребро <tex> e = UVuv </tex>, получим гамильтонов граф '''<tex> G''' + UVe</tex>.Рассмотрим [[Гамильтоновы графы|гамильтонов цикл]] графа '''<tex> G''' + UV e</tex> : в нем обязательно присутствует ребро UV<tex> e </tex>. <br>Отбрасывая ребро UV<tex> e </tex>, получим гамильтонову (U<tex>u</tex>, V<tex>v</tex>)-цепь в графе '''<tex> G''' </tex> : <tex>\ U u = U_1 u_1 - U_2 u_2 - ... - U_n u_n = V v </tex>. <br>Пусть <tex>\ S = \{i|e_i = U_1 U_u_1 u_{i+1} \in E(G)\} </tex> <br>Пусть <tex>\ T = \{i|f_i = U_i U_n u_i u_n \in E(G)\} </tex> <br> <tex>\ S \cap T = \empty varnothing </tex>, иначе в графе '''<tex> G''' </tex> есть гамильтонов цикл. Пусть j <tex> \in S \cap T </tex>. Тогда получим гамильтонов цикл графа '''<tex> G''' </tex> : <tex>\ U_1 u_1 - U_u_{j+1} - U_u_{j+2} - ... - U_n u_n - U_j u_j - U_u_{j-1} - ... - U_1 u_1 </tex> <br>Из определений <tex>\ S </tex> и <tex>\ T </tex> следует, что <tex>\ S \cup T \subseteq \{1, 2, ..., n - 1 \} </tex> , поэтому <tex>2\ 2degU deg u \le degU \deg u + degV \deg v = |S| + |T| = |S \cup T| < n </tex>, т.е. то есть <tex>\ degU deg u < n/2 </tex> <br>Т.к. Так как <tex>\ S \cap T = \empty varnothing </tex>, ни одна вершина <tex>\ U_j u_j </tex> не смежна с <tex>\ V v = U_n u_n </tex> (для <tex>\ j \in S </tex>). Отсюда в силу выбора <tex>\ U u </tex> и <tex>\ V v </tex> имеем <tex>\ degU_j deg u_j \le degU \deg u </tex>. Положим <tex>\ k = degU \deg u </tex>.Тогда имеется по крайней мере <tex>\ |S| = degU \deg u = k </tex> вершин, степень которых не превосходит k. <br>
В силу леммы(I) выполняется : <tex>\ d_k \le k < n/2 </tex> <br>
По условию <tex>\ (*) </tex> получаем : <tex>\ d_{n-k} \ge n-k </tex> <br>
В силу леммы(II) имеется по крайней мере <tex>\ k+1 </tex> вершин, степень которых не меньше <tex>\ n-k </tex> <br>
Так как <tex>\ k = \deg U u </tex>, то вершина <tex>\ U u </tex> может быть смежна, самое большее, с <tex>\ k </tex> из этих <tex>\ k+1 </tex> вершин. Значит существует вершина <tex>\ W w </tex>, несмежная с <tex>\ U u </tex>, и для которой <tex>\ degW deg w \ge n-k </tex>. Но тогда получим <tex>\deg U u + \deg W w \ge k + (n - k) = n > \deg U u + \deg V v </tex>, что противоречит выбору <tex>\ U u </tex> и <tex>\ V v </tex>. <br>
}}
==Литература==
* Асанов М,, Баранский В., Расин В. - Дискретная математика - Графы, матроиды, алгоритмы
