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

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 1: Строка 1:
Дан [[Основные определения теории графов|граф]] <tex> G </tex>, состоящий из <tex>\ n </tex> [[Основные определения теории графов|вершин]], <tex>\ d_i </tex> - [[Основные определения теории графов|степень]] <tex>\ i </tex> - ой вершины. <br>
+
Дан [[Основные определения теории графов|граф]] <tex> G </tex>, состоящий из <tex>\ n </tex> [[Основные определения теории графов|вершин]], <tex>\ d_i </tex> [[Основные определения теории графов|степень]] <tex>\ i </tex> - ой вершины. <br>
 
Все <tex>\ d_i </tex> расположены в порядке неубывания. <br>
 
Все <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>\ (*): </tex> <tex>\forall k</tex> верна импликация <tex>(d_k \le k < n/2 \Rightarrow d_{n-k} \ge n-k)</tex> <br>
Строка 9: Строка 9:
 
Верно и обратное утверждение.
 
Верно и обратное утверждение.
 
|proof=
 
|proof=
Так как <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>
+
Так как <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>
 
Пусть у нас есть <tex>\ n </tex> вершин. Из них <tex>\ k + p (p \ge 0) </tex> вершин имеют степень не больше <tex>\ k </tex>.
 
Пусть у нас есть <tex>\ n </tex> вершин. Из них <tex>\ k + p (p \ge 0) </tex> вершин имеют степень не больше <tex>\ k </tex>.
Строка 23: Строка 23:
 
Верно и обратное утверждение.
 
Верно и обратное утверждение.
 
|proof=
 
|proof=
Так как <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>
+
Так как <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>
 
Пусть у нас есть <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>.   
 
Пусть у нас есть <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>.   
Строка 33: Строка 33:
 
III
 
III
 
|statement=
 
|statement=
Пусть <tex>\ (*) </tex> выполнена для последовательности <tex>\ d_1, d_2, ... , d_n </tex>.  
+
# Пусть <tex>\ (*) </tex> выполнена для последовательности <tex>\ d_1, d_2, ... , d_n </tex>.  
Пусть <tex>\ d_1 \le d_1' , ... , d_n \le d_n' </tex>.
+
# Пусть <tex>\ d_1 \le d_1' , ... , d_n \le d_n' </tex>.
 
Тогда <tex>\ (*) </tex> выполнена и для <tex>\ d_1', ... , d_n' </tex>
 
Тогда <tex>\ (*) </tex> выполнена и для <tex>\ d_1', ... , d_n' </tex>
 
}}
 
}}
 +
<br>
 
{{Лемма
 
{{Лемма
 
|about=
 
|about=
 
IV
 
IV
 
|statement=
 
|statement=
>Если условие <tex>\ (*) </tex> верно для некоторой последовательности степеней, то оно верно и для мажорирующей ее последовательности.
+
Если условие <tex>\ (*) </tex> верно для некоторой последовательности степеней, то оно верно и для мажорирующей её последовательности.
 
}}
 
}}
 +
<br>
 
{{Теорема
 
{{Теорема
 
|about=
 
|about=
 
Хватал
 
Хватал
 
|statement=
 
|statement=
Пусть <tex> G </tex> - [[Отношение связности, компоненты связности|связный граф]], количество вершин которого не меньше 3. Упорядочим степени вершин <tex>\ G </tex> по неубыванию.
+
Пусть <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>  (*)  </tex>, то <tex> G </tex> - [[Гамильтоновы графы|гамильтонов]].
+
Если для <tex>\forall k</tex> верна импликация <tex>(d_k \le k < n/2 \Rightarrow d_{n-k} \ge n-k) </tex> <tex>  (*)  </tex>, то <tex> G </tex> [[Гамильтоновы графы|гамильтонов]].
 
|proof=
 
|proof=
 
Приведем доказательство от противного.
 
Приведем доказательство от противного.
Строка 56: Строка 58:
 
Очевидно, что граф <tex>\ K_n </tex> гамильтонов для <tex>\ k \ge 3 </tex>.
 
Очевидно, что граф <tex>\ K_n </tex> гамильтонов для <tex>\ k \ge 3 </tex>.
 
Будем считать <tex> G </tex> максимальным негамильтоновым остовным подграфом графа <tex>\ K_n </tex>.
 
Будем считать <tex> G </tex> максимальным негамильтоновым остовным подграфом графа <tex>\ K_n </tex>.
Выберем две несмежные вершины <tex> u </tex> и <tex> v </tex> графа <tex> G </tex> с условием : <tex> \deg u + \deg v </tex> - максимально.
+
Выберем две несмежные вершины <tex> u </tex> и <tex> v </tex> графа <tex> G </tex> с условием : <tex> \deg u + \deg v </tex> максимально.
 
Будем считать, <tex>\deg u \le \deg v </tex>.
 
Будем считать, <tex>\deg u \le \deg v </tex>.
 
Добавив к <tex> G </tex> новое ребро <tex> e = uv </tex>, получим гамильтонов граф <tex> G + e</tex>.
 
Добавив к <tex> G </tex> новое ребро <tex> e = uv </tex>, получим гамильтонов граф <tex> G + e</tex>.
Строка 65: Строка 67:
 
<tex>\ S \cap T  = \varnothing </tex>, иначе в графе <tex> G </tex> есть гамильтонов цикл. Пусть j <tex> \in S \cap T </tex>. Тогда получим гамильтонов цикл графа <tex> G </tex> : <tex>\ u_1 - u_{j+1} - u_{j+2} - ... - u_n - u_j - u_{j-1} - ... - u_1 </tex>.
 
<tex>\ S \cap T  = \varnothing </tex>, иначе в графе <tex> G </tex> есть гамильтонов цикл. Пусть j <tex> \in S \cap T </tex>. Тогда получим гамильтонов цикл графа <tex> G </tex> : <tex>\ u_1 - u_{j+1} - u_{j+2} - ... - u_n - u_j - u_{j-1} - ... - u_1 </tex>.
 
Из определений <tex>\ S </tex> и <tex>\ T </tex> следует, что <tex>\ S \cup T \subseteq \{1, 2, ..., n - 1 \} </tex> , поэтому <tex> 2\deg u \le \deg u + \deg v = |S| + |T| = |S \cup T| < n </tex>, то есть <tex>\deg u < n/2 </tex>. <br>
 
Из определений <tex>\ S </tex> и <tex>\ T </tex> следует, что <tex>\ S \cup T \subseteq \{1, 2, ..., n - 1 \} </tex> , поэтому <tex> 2\deg u \le \deg u + \deg v = |S| + |T| = |S \cup T| < n </tex>, то есть <tex>\deg u < n/2 </tex>. <br>
Так как <tex>\ S \cap T  = \varnothing </tex>, ни одна вершина <tex>\ u_j </tex> не смежна с <tex>\ v = u_n </tex> (для <tex>\ j \in S </tex>). Отсюда в силу выбора <tex> u </tex> и <tex> v </tex> имеем <tex>\deg u_j \le \deg u </tex>. Положим <tex>\ k = \deg u </tex>.
+
Так как <tex>\ S \cap T  = \varnothing </tex>, ни одна вершина <tex>\ u_j </tex> не смежна с <tex>\ v = u_n </tex> (для <tex>\ j \in S </tex>). Отсюда в силу выбора <tex> u </tex> и <tex> v </tex> имеем <tex>\deg u_j \le \deg u </tex>. Положим, что <tex>\ k = \deg u </tex>.
 
Тогда имеется по крайней мере <tex>\ |S| = \deg u = k </tex> вершин, степень которых не превосходит k. <br>
 
Тогда имеется по крайней мере <tex>\ |S| = \deg u = k </tex> вершин, степень которых не превосходит k. <br>
 
В силу леммы(I) выполняется : <tex>\ d_k \le k < n/2 </tex>. <br>
 
В силу леммы(I) выполняется : <tex>\ d_k \le k < n/2 </tex>. <br>
 
По условию <tex>\ (*) </tex> получаем : <tex>\ d_{n-k} \ge n-k </tex>. <br>
 
По условию <tex>\ (*) </tex> получаем : <tex>\ d_{n-k} \ge n-k </tex>. <br>
 
В силу леммы(II) имеется по крайней мере <tex>\ k+1 </tex> вершин, степень которых не меньше <tex>\ n-k </tex>. <br>
 
В силу леммы(II) имеется по крайней мере <tex>\ k+1 </tex> вершин, степень которых не меньше <tex>\ n-k </tex>. <br>
Так как <tex>\ k = \deg u </tex>, то вершина <tex>\ u </tex> может быть смежна, самое большее, с <tex>\ k </tex> из этих <tex>\ k+1 </tex> вершин. Значит существует вершина <tex>\ w </tex>, несмежная с <tex>\ u </tex>, и для которой <tex>\deg w \ge n-k </tex>. Но тогда получим <tex>\deg u + \deg w \ge k + (n - k) = n > \deg u + \deg v </tex>, что противоречит выбору <tex>\ u </tex> и <tex>\ v </tex>. <br>  
+
Так как <tex>\ k = \deg u </tex>, то вершина <tex>\ u </tex> может быть смежна не больше, чем с <tex>\ k </tex> из этих <tex>\ k+1 </tex> вершин. Значит существует вершина <tex>\ w </tex>, не являющаяся смежной с <tex>\ u </tex> и для которой <tex>\deg w \ge n-k </tex>. Но тогда получим <tex>\deg u + \deg w \ge k + (n - k) = n > \deg u + \deg v </tex>, что противоречит выбору <tex>\ u </tex> и <tex>\ v </tex>. <br>  
 
}}
 
}}
  

Версия 00:12, 15 октября 2011

Дан граф [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]. Если [math] p = 1 [/math], то [math] n-k-p+1 = n-k [/math]. Отсюда видно, что [math]\ d_{n-k} \ge n-k [/math].
[math]\triangleleft[/math]


Лемма (III):
# Пусть [math]\ (*) [/math] выполнена для последовательности [math]\ d_1, d_2, ... , d_n [/math].
  1. Пусть [math]\ d_1 \le d_1' , ... , d_n \le d_n' [/math].
Тогда [math]\ (*) [/math] выполнена и для [math]\ d_1', ... , d_n' [/math]


Лемма (IV):
Если условие [math]\ (*) [/math] верно для некоторой последовательности степеней, то оно верно и для мажорирующей её последовательности.


Теорема (Хватал):
Пусть [math] G [/math]связный граф, количество вершин которого не меньше 3. Упорядочим степени вершин [math]\ G [/math] по неубыванию. Если для [math]\forall k[/math] верна импликация [math](d_k \le k \lt n/2 \Rightarrow d_{n-k} \ge n-k) [/math] [math] (*) [/math], то [math] G [/math]гамильтонов.
Доказательство:
[math]\triangleright[/math]

Приведем доказательство от противного. Пусть теорема Хватала не верна, есть граф, где [math]\ n \ge 3 [/math], удовлетворяющий условию [math]\ (*) [/math], но не гамильтонов. Будем добавлять в него ребра до тех пор, пока не получим максимально возможный негамильтонов граф [math] G [/math](то есть добавление еще одного ребра сделает граф [math] G [/math] гамильтоновым). Добавление ребер не противоречит условию [math]\ (*) [/math]. Очевидно, что граф [math]\ K_n [/math] гамильтонов для [math]\ k \ge 3 [/math]. Будем считать [math] G [/math] максимальным негамильтоновым остовным подграфом графа [math]\ K_n [/math]. Выберем две несмежные вершины [math] u [/math] и [math] v [/math] графа [math] G [/math] с условием : [math] \deg u + \deg v [/math] — максимально. Будем считать, [math]\deg u \le \deg v [/math]. Добавив к [math] G [/math] новое ребро [math] e = uv [/math], получим гамильтонов граф [math] G + e[/math]. Рассмотрим гамильтонов цикл графа [math] G + e[/math] : в нем обязательно присутствует ребро [math] e [/math].
Отбрасывая ребро [math] e [/math], получим гамильтонову ([math]u[/math], [math]v[/math])-цепь в графе [math] G [/math] : [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 = \varnothing [/math], иначе в графе [math] G [/math] есть гамильтонов цикл. Пусть j [math] \in S \cap T [/math]. Тогда получим гамильтонов цикл графа [math] G [/math] : [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] 2\deg u \le \deg u + \deg v = |S| + |T| = |S \cup T| \lt n [/math], то есть [math]\deg u \lt n/2 [/math].
Так как [math]\ S \cap T = \varnothing [/math], ни одна вершина [math]\ u_j [/math] не смежна с [math]\ v = u_n [/math] (для [math]\ j \in S [/math]). Отсюда в силу выбора [math] u [/math] и [math] v [/math] имеем [math]\deg u_j \le \deg u [/math]. Положим, что [math]\ k = \deg u [/math]. Тогда имеется по крайней мере [math]\ |S| = \deg u = 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 = \deg u [/math], то вершина [math]\ u [/math] может быть смежна не больше, чем с [math]\ k [/math] из этих [math]\ k+1 [/math] вершин. Значит существует вершина [math]\ w [/math], не являющаяся смежной с [math]\ u [/math] и для которой [math]\deg w \ge n-k [/math]. Но тогда получим [math]\deg u + \deg w \ge k + (n - k) = n \gt \deg u + \deg v [/math], что противоречит выбору [math]\ u [/math] и [math]\ v [/math].
[math]\triangleleft[/math]

Литература

  • Асанов М,, Баранский В., Расин В. - Дискретная математика - Графы, матроиды, алгоритмы