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

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 5: Строка 5:
 
Пусть <tex> G </tex> — [[Отношение связности, компоненты связности|связный граф]], <tex> n = |VG| \geq 3 </tex> — количество вершин, <tex> d_1 \leq d_2 \leq \ldots \leq d_n </tex> — последовательность степеней. <br>
 
Пусть <tex> G </tex> — [[Отношение связности, компоненты связности|связный граф]], <tex> n = |VG| \geq 3 </tex> — количество вершин, <tex> d_1 \leq d_2 \leq \ldots \leq d_n </tex> — последовательность степеней. <br>
 
Если <tex> \forall k \in \mathbb N </tex> верна импликация: <br>
 
Если <tex> \forall k \in \mathbb N </tex> верна импликация: <br>
<center><tex> d_k \leq k < n/2 \rightarrow d_{n-k} \geq n-k, (*)</tex></center><br>
+
<center><tex> d_k \leq k < n/2 \rightarrow d_{n - k} \geq n - k, (*)</tex></center><br>
 
то граф <tex> G </tex> [[Гамильтоновы графы|гамильтонов]].
 
то граф <tex> G </tex> [[Гамильтоновы графы|гамильтонов]].
 
|proof=
 
|proof=
 
Для доказательства теоремы, докажем 3 леммы.
 
Для доказательства теоремы, докажем 3 леммы.
# {{Лемма
+
{{Лемма
 +
|about=
 +
1
 
|statement=
 
|statement=
<tex>\ d_k \leq k \Leftrightarrow |\{ v \in |VG| : d_v \leq k \}| \geq k</tex>.
+
<tex> d_k \leq k \Leftrightarrow |\{ v \in VG : d_v \leq k \}| \geq k. </tex>
 
|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> \Rightarrow </tex>" Пусть <tex> d_1 \leq d_2 \leq \ldots \leq d_k, d_k \leq k, |\{ d_1, d_2, \ldots, d_k \}| = k </tex>. <br>
'''Доказательство в обратную сторону:''' <br>
+
<tex> \{ d_1, d_2, \ldots, d_k \} \subset \{ v \in VG : d_v \leq k \} \Rightarrow |\{ v \in VG : d_v \leq k \}| \geq k </tex>, q.e.d.
пусть у нас есть <tex>\ n </tex> вершин. Из них <tex>\ k + p </tex> <tex> (p \ge 0) </tex> имеют степень не больше <tex>\ k </tex>.
 
Расположим вершины в неубывающем порядке их степеней. <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>.
 
}}
 
  
# {{Лемма
+
* "<tex> \Leftarrow </tex>" Пусть <tex> |\{ v \in VG : d_v \leq k \}| = k + p, p \geq 0 </tex>. Расположим вершины в неубывающем порядке их степеней. <br>
|statement=
+
<tex> d_1 \leq d_2 \leq \ldots \leq d_k \leq \ldots \leq d_{k + p} \leq k \Rightarrow d_k \leq k </tex>, q.e.d.
Если <tex>\ d_{n-k} \ge n-k </tex>, то число вершин, степень которых не меньше <tex>\ n-k </tex>, больше или равно <tex>\ k+1 </tex>.
 
Верно и обратное утверждение.
 
|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>
 
'''Доказательство в обратную сторону:''' <br>
 
пусть у нас есть <tex>\ n </tex> вершин. Из них <tex>\ k+p </tex> <tex> (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>.
 
 
}}
 
}}
}}
 
 
 
{{Лемма
 
{{Лемма
 
|about=
 
|about=
III
+
2
 
|statement=
 
|statement=
Пусть верно следующее:
+
<tex>\ d_{n - k} \geq n - k \Leftrightarrow |\{ v \in VG : d_v \geq n - k \}| \geq k + 1. </tex>
# <tex> (*) </tex> выполнено для последовательности <tex>\ d_1, d_2, ... , d_n </tex>.
+
|proof=
# <tex>\ d_1 \le d_1' , ... , d_n \le d_n' </tex>.
+
* "<tex> \Rightarrow </tex>" Пусть <tex> d_{n - k} \geq n - k, \leq d_{n - k} \leq d_{n - k + 1} \leq \ldots \leq d_n, |\{ d_{n - k}, d_{n - k + 1}, \ldots , d_n \}| = k + 1 </tex><br>
Тогда <tex>\ (*) </tex> выполнено и для <tex>\ d_1', ... , d_n' </tex>.
+
<tex> \{ d_{n - k}, d_{n - k + 1}, \ldots , d_n \} \subset \{ v \in VG : d_v \geq n - k \} \Rightarrow \{ v \in VG : d_v \geq n - k \} \geq k + 1 </tex>, q.e.d.
 +
 
 +
* "<tex> \Leftarrow </tex>" Пусть <tex> |\{ v \in VG : d_v \geq n - k \}| = k + 1 + p, p \geq 0 </tex>. Расположим вершины в неубывающем порядке их степеней. <br>
 +
<tex> d_n \geq d_{n - 1} \ldots \geq d_{n - k} \geq \ldots \geq d_{n - k - p} \geq n - k \Rightarrow d_{n - k} \geq n - k </tex>, q.e.d.
 
}}
 
}}
 
{{Лемма
 
{{Лемма
 
|about=
 
|about=
IV
+
3
 
|statement=
 
|statement=
Если <tex>\ (*) </tex> верно для некоторой последовательности степеней, то оно верно и для мажорирующей её последовательности.
+
Если импликация <tex> (*) </tex> верна для некоторой последовательности степеней <tex> d </tex>, то она верна и для неубывающей последовательности <tex> d' </tex>, мажорирующей <tex> d </tex>.
 
}}
 
}}
{{Теорема
+
 
|about=
 
Хватал
 
|statement=
 
Пусть <tex> G </tex> — [[Отношение связности, компоненты связности|связный граф]], количество вершин которого не меньше 3. Упорядочим степени вершин <tex>\ G </tex> по неубыванию.
 
Если <tex>\forall k</tex> верно <tex> (*) </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>\ n \ge 3 </tex>, удовлетворяющий <tex>\ (*) </tex>, но негамильтонов.
Строка 76: Строка 64:
  
 
==Литература==
 
==Литература==
* Асанов М,, Баранский В., Расин В. Дискретная математика Графы, матроиды, алгоритмы
+
* Асанов М., Баранский В., Расин В.: ''Дискретная математика: Графы, матроиды, алгоритмы''
  
 
[[Категория: Алгоритмы и структуры данных]]
 
[[Категория: Алгоритмы и структуры данных]]
 
[[Категория: Обходы графов]]
 
[[Категория: Обходы графов]]

Версия 05:54, 18 ноября 2011

Теорема (Хватал):
Пусть [math] G [/math]связный граф, [math] n = |VG| \geq 3 [/math] — количество вершин, [math] d_1 \leq d_2 \leq \ldots \leq d_n [/math] — последовательность степеней.

Если [math] \forall k \in \mathbb N [/math] верна импликация:

[math] d_k \leq k \lt n/2 \rightarrow d_{n - k} \geq n - k, (*)[/math]

то граф [math] G [/math] гамильтонов.
Доказательство:
[math]\triangleright[/math]

Для доказательства теоремы, докажем 3 леммы.

Лемма (1):
[math] d_k \leq k \Leftrightarrow |\{ v \in VG : d_v \leq k \}| \geq k. [/math]
Доказательство:
[math]\triangleright[/math]
  • "[math] \Rightarrow [/math]" Пусть [math] d_1 \leq d_2 \leq \ldots \leq d_k, d_k \leq k, |\{ d_1, d_2, \ldots, d_k \}| = k [/math].

[math] \{ d_1, d_2, \ldots, d_k \} \subset \{ v \in VG : d_v \leq k \} \Rightarrow |\{ v \in VG : d_v \leq k \}| \geq k [/math], q.e.d.

  • "[math] \Leftarrow [/math]" Пусть [math] |\{ v \in VG : d_v \leq k \}| = k + p, p \geq 0 [/math]. Расположим вершины в неубывающем порядке их степеней.
[math] d_1 \leq d_2 \leq \ldots \leq d_k \leq \ldots \leq d_{k + p} \leq k \Rightarrow d_k \leq k [/math], q.e.d.
[math]\triangleleft[/math]
Лемма (2):
[math]\ d_{n - k} \geq n - k \Leftrightarrow |\{ v \in VG : d_v \geq n - k \}| \geq k + 1. [/math]
Доказательство:
[math]\triangleright[/math]
  • "[math] \Rightarrow [/math]" Пусть [math] d_{n - k} \geq n - k, \leq d_{n - k} \leq d_{n - k + 1} \leq \ldots \leq d_n, |\{ d_{n - k}, d_{n - k + 1}, \ldots , d_n \}| = k + 1 [/math]

[math] \{ d_{n - k}, d_{n - k + 1}, \ldots , d_n \} \subset \{ v \in VG : d_v \geq n - k \} \Rightarrow \{ v \in VG : d_v \geq n - k \} \geq k + 1 [/math], q.e.d.

  • "[math] \Leftarrow [/math]" Пусть [math] |\{ v \in VG : d_v \geq n - k \}| = k + 1 + p, p \geq 0 [/math]. Расположим вершины в неубывающем порядке их степеней.
[math] d_n \geq d_{n - 1} \ldots \geq d_{n - k} \geq \ldots \geq d_{n - k - p} \geq n - k \Rightarrow d_{n - k} \geq n - k [/math], q.e.d.
[math]\triangleleft[/math]
Лемма (3):
Если импликация [math] (*) [/math] верна для некоторой последовательности степеней [math] d [/math], то она верна и для неубывающей последовательности [math] d' [/math], мажорирующей [math] d [/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] есть гамильтонов цикл: пусть z [math] \in S \cap T [/math]. Тогда получим гамильтонов цикл графа [math] G [/math]: [math]\ u_1 - u_{z+1} - u_{z+2} - ... - u_n - u_z - u_{z-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.
В силу первой леммы, выполняется: [math]\ d_k \le k \lt n/2 [/math].
Исходя из [math]\ (*) [/math], получаем: [math]\ d_{n-k} \ge n-k [/math].
В силу второй леммы, имеется по крайней мере [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]

Литература

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