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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Литература)
Строка 127: Строка 127:
 
* [[Теорема Оре]]
 
* [[Теорема Оре]]
  
== Литература ==
+
== Источники информации ==
 
* Асанов М., Баранский В., Расин В.: ''Дискретная математика: Графы, матроиды, алгоритмы''
 
* Асанов М., Баранский В., Расин В.: ''Дискретная математика: Графы, матроиды, алгоритмы''
  
 
[[Категория: Алгоритмы и структуры данных]]
 
[[Категория: Алгоритмы и структуры данных]]
 
[[Категория: Обходы графов]]
 
[[Категория: Обходы графов]]

Версия 19:32, 11 ноября 2015

Определение:
Пусть неориентированный граф [math] G [/math] имеет [math] n [/math] вершин: [math] v_1, v_2, \ldots, v_n [/math]. Пусть [math] d_i = \deg v_i \mbox{ } (i = \overline{1, n}) [/math] и вершины графа упорядочены таким образом, что [math] d_1 \leq d_2 \leq \ldots \leq d_n [/math]. Последовательность [math] d_1, d_2, \ldots, d_n [/math] называют последовательностью степеней графа [math] G [/math].


Лемма (О добавлении ребра в граф):
Пусть неориентированный граф [math] G' [/math] получен из неориентированного графа [math] G [/math] добавлением одного нового ребра [math] e [/math]. Тогда последовательность степеней графа [math] G [/math] мажорируется последовательностью степеней графа [math] G' [/math].
Доказательство:
[math]\triangleright[/math]

Замечание: Если в неубывающей последовательности [math] d_1, d_2, \ldots, d_n [/math] увеличить на единицу число [math] d_i [/math], а затем привести последовательность к неубывающему виду, переставив число [math] d_i + 1 [/math] на положенное место [math] j [/math], то исходная последовательность будет мажорироваться полученной. Если [math]j = i[/math], то утверждение леммы, очевидно, выполняется. Пусть [math]j \neq i[/math].

Исходная последовательность степеней [math] d [/math]
  • Рассмотрим элементы с номерами [math] s = \overline{1, i - 1} [/math]. Они не изменились, следовательно мажорируются собой.
  • Рассмотрим элементы с номерами [math] s = \overline{i, j - 1} [/math]. [math] s [/math]-й элемент полученной последовательности равен [math] s + 1 [/math]-му элементу исходной. [math] d_s \leq d_{s + 1} \Rightarrow d_s \leq d'_s = d_{s + 1} [/math].
  • Расмотрим [math]j[/math]-ый элемент. Имеем [math]d'_j \ge d'_{j-1} = d_{j} [/math].
  • Рассмотрим элементы с номерами [math] s = \overline{j + 1, n} [/math]. Они не изменились, следовательно мажорируются собой.
Новая последовательность степеней [math] d' [/math]

При добавлении в граф ребра [math] e = uv, \mbox{ } (u \neq v) [/math], степени вершин [math] u [/math] и [math] v [/math] увеличатся на единицу. Для доказательства леммы, дважды воспользуемся замечанием.

Значит, последовательность степеней полученного графа мажорирует последовательность степеней исходного, q.e.d.
[math]\triangleleft[/math]
Теорема (Хватал):
Пусть:
  • [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 [/math],
  • [math] d_k \leq k [/math],
  • [math] |\{ d_1, d_2, \ldots, d_k \}| = k [/math].

[math] \{ d_1, d_2, \ldots, d_k \} \subseteq \{ 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 [/math],
  • [math] 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 [/math],
  • [math] d_{n - k} \leq d_{n - k + 1} \leq \ldots \leq d_n [/math],
  • [math] |\{ d_{n - k}, d_{n - k + 1}, \ldots , d_n \}| = k + 1 [/math].

[math] \{ d_{n - k}, d_{n - k + 1}, \ldots , d_n \} \subseteq \{ 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]\triangleright[/math]
  1. Пусть [math] d'_k \gt k [/math]. Тогда первый аргумент импликации всегда ложен, следовательно импликация верна вне зависимости от второго аргумента. Значит, в этом случае импликация [math] (*) [/math] верна для последовательности [math] d' [/math].
  2. Пусть [math] d'_k \leq k, \mbox{ } d'_{n - k} \geq d_{n - k} \geq n - k [/math]. Тогда оба аргумента импликации всегда истинны. Значит, и в этом случае импликация [math] (*) [/math] верна для последовательности [math] d' [/math].
Значит, импликация [math] (*) [/math] выполняется и для последовательности [math] d' [/math], q.e.d.
[math]\triangleleft[/math]

Приведем доказательство от противного.

Пусть существует граф с числом вершин [math] n \geq 3 [/math], удовлетворяющий [math] (*) [/math], но негамильтонов. Будем добавлять в него ребра до тех пор, пока не получим максимально возможный негамильтонов граф [math] G [/math] (то есть добавление еще одного ребра сделает граф [math] G [/math] гамильтоновым). По лемме о добавлении ребра и лемме №3 импликация [math] (*) [/math] остается верной для графа [math] G [/math]. Очевидно, что граф [math]\ K_n [/math] гамильтонов при [math] k \geq 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 \leq \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, v) [/math]-цепь в графе [math] G [/math]: [math] u = u_1 \rightarrow u_2 \rightarrow \ldots \rightarrow u_n = v [/math].

Пусть [math] S = \{ i | e_i = u_1 u_{i + 1} \in EG\}, T = \{ i |f_i = u_i u_n \in EG\} [/math].

Множество [math] S [/math] обозначено красным цветом, множество [math] T [/math] обозначено синим цветом
Утверждение:
[math] S \cap T = \emptyset [/math].
[math]\triangleright[/math]

Пусть [math] j \in S \cap T [/math]. Тогда получим гамильтонов цикл графа [math] G [/math]: [math] u_1 \xrightarrow{e_j} u_{j + 1} \rightarrow \ldots \rightarrow u_n \xrightarrow{f_j} u_j \rightarrow u_{j - 1} \rightarrow \ldots \rightarrow u_1 [/math], что противоречит условию, что граф негамильтонов.

Hvatal 4.png
Значит, [math] S \cap T [/math], q.e.d.
[math]\triangleleft[/math]

Из определений [math] S [/math] и [math] T [/math] следует, что [math] S \cup T \subseteq \{1, 2, ..., n - 1 \} \Rightarrow 2 \deg u \leq \deg u + \deg v = |S| + |T| = |S \cup T| \lt n [/math]. Значит, [math] \deg u \lt n/2 [/math].

Так как [math] S \cap T = \emptyset [/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 \leq \deg u [/math]. Пусть [math] k = \deg u = |S| [/math]. Значит, [math] \exists k [/math] вершин, степень которых не превосходит [math] k [/math].

По лемме №1: [math] d_k \leq k \lt n/2 [/math]. В силу импликации [math] (*) [/math]: [math] d_{n - k} \geq n - k [/math].

По лемме №2, [math] \exists 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 \geq n - k [/math]. Тогда получим, что [math] \deg u + \deg w \geq k + (n - k) = n \gt \deg u + \deg v [/math], что противоречит выбору [math] u [/math] и [math] v [/math].

Значит, предположение неверно, q.e.d.
[math]\triangleleft[/math]

См. также

Источники информации

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