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

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 10: Строка 10:
 
Пусть неориентированный граф <tex> G' </tex> получен из неориентированного графа <tex> G </tex> добавлением одного нового ребра <tex> e </tex>. Тогда последовательность степеней графа <tex> G </tex> мажорируется последовательностью степеней графа <tex> G' </tex>.
 
Пусть неориентированный граф <tex> G' </tex> получен из неориентированного графа <tex> G </tex> добавлением одного нового ребра <tex> e </tex>. Тогда последовательность степеней графа <tex> G </tex> мажорируется последовательностью степеней графа <tex> G' </tex>.
 
|proof=
 
|proof=
''Замечание'': Если в неубывающей последовательности <tex> d_1, d_2, \ldots, d_n </tex> увеличить на единицу число <tex> d_i </tex>, а затем привести последовательность к неубывающему виду, переставив число <tex> d_i + 1 </tex> на положенное место, то исходная последовательность будет мажорироваться полученной.
+
''Замечание'': Если в неубывающей последовательности <tex> d_1, d_2, \ldots, d_n </tex> увеличить на единицу число <tex> d_i </tex>, а затем привести последовательность к неубывающему виду, переставив число <tex> d_i + 1 </tex> на положенное место <tex> j </tex>, то исходная последовательность будет мажорироваться полученной.
 +
* Рассмотрим элементы с номерами <tex> s = \overline{1, i} </tex>. Они не изменились, следовательно мажорируются собой.
 +
* Рассмотрим элементы с номерами <tex> s = \overline{i + 1, j + 1} </tex>. <tex> s + 1 </tex>-й элемент исходной последовательности равен <tex> s </tex>-му элементу полученной. <tex> d_s \leq d_{s + 1} \Rightarrow d_s \leq d'_s </tex>.
 +
* Рассмотрим элементы с номерами <tex> s = \overline{j + 1, n} </tex>. Они не изменились, следовательно мажорируются собой.
 
При добавлении в граф ребра <tex> e = uv, \mbox{ } (u \neq v) </tex>, степени вершин <tex> u </tex> и <tex> v </tex> увеличатся на единицу. Для доказательства леммы, дважды воспользуемся замечанием.
 
При добавлении в граф ребра <tex> e = uv, \mbox{ } (u \neq v) </tex>, степени вершин <tex> u </tex> и <tex> v </tex> увеличатся на единицу. Для доказательства леммы, дважды воспользуемся замечанием.
 
Значит, последовательность степеней полученного графа мажорирует последовательность степеней исходного, q.e.d.
 
Значит, последовательность степеней полученного графа мажорирует последовательность степеней исходного, q.e.d.

Версия 17:44, 23 ноября 2011

Определение:
Пусть неориентированный граф [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] s = \overline{1, i} [/math]. Они не изменились, следовательно мажорируются собой.
  • Рассмотрим элементы с номерами [math] s = \overline{i + 1, j + 1} [/math]. [math] s + 1 [/math]-й элемент исходной последовательности равен [math] s [/math]-му элементу полученной. [math] d_s \leq d_{s + 1} \Rightarrow d_s \leq d'_s [/math].
  • Рассмотрим элементы с номерами [math] s = \overline{j + 1, n} [/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 [/math],
  • [math] 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 \cap T = \emptyset [/math].
[math]\triangleright[/math]
Пусть [math] j \in S \cap T [/math]. Тогда получим гамильтонов цикл графа [math] G [/math]: [math] u_1 \rightarrow^{e_j} u_{j + 1} \rightarrow u_{j + 2} \rightarrow \ldots \rightarrow u_n \rightarrow^{f_j} u_j \rightarrow u_{j - 1} \rightarrow \ldots \rightarrow u_1 [/math], что противоречит условию, что граф негамильтонов. Значит, [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 [/math] ровно [math] 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]

Литература

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