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

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 11: Строка 11:
 
|proof=
 
|proof=
 
''Замечание'': Если в неубывающей последовательности <tex> d_1, d_2, \ldots, d_n </tex> увеличить на единицу число <tex> d_i </tex>, а затем привести последовательность к неубывающему виду, переставив число <tex> d_i + 1 </tex> на положенное место <tex> j </tex>, то исходная последовательность будет мажорироваться полученной. Если <tex>j = i</tex>, то утверждение леммы, очевидно, выполняется. Пусть <tex>j \neq i</tex>.
 
''Замечание'': Если в неубывающей последовательности <tex> d_1, d_2, \ldots, d_n </tex> увеличить на единицу число <tex> d_i </tex>, а затем привести последовательность к неубывающему виду, переставив число <tex> d_i + 1 </tex> на положенное место <tex> j </tex>, то исходная последовательность будет мажорироваться полученной. Если <tex>j = i</tex>, то утверждение леммы, очевидно, выполняется. Пусть <tex>j \neq i</tex>.
[[Файл: Hvatal_1.png|500px|thumb|center|Исходная последовательность степеней <tex> d </tex>]]
+
[[Файл: Hvatal_1.png|270px|thumb|center|Исходная последовательность степеней <tex> d </tex>]]
  
 
* Рассмотрим элементы с номерами <tex> s = \overline{1, i - 1} </tex>. Они не изменились, следовательно мажорируются собой.
 
* Рассмотрим элементы с номерами <tex> s = \overline{1, i - 1} </tex>. Они не изменились, следовательно мажорируются собой.
Строка 17: Строка 17:
 
* Расмотрим <tex>j</tex>-ый элемент. Имеем <tex>d'_j \ge d'_{j-1} = d_{j} </tex>.
 
* Расмотрим <tex>j</tex>-ый элемент. Имеем <tex>d'_j \ge d'_{j-1} = d_{j} </tex>.
 
* Рассмотрим элементы с номерами <tex> s = \overline{j + 1, n} </tex>. Они не изменились, следовательно мажорируются собой.
 
* Рассмотрим элементы с номерами <tex> s = \overline{j + 1, n} </tex>. Они не изменились, следовательно мажорируются собой.
[[Файл: Hvatal_2.png|500px|thumb|center|Новая последовательность степеней <tex> d' </tex>]]
+
[[Файл: Hvatal_2.png|290px|thumb|center|Новая последовательность степеней <tex> d' </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.
Строка 98: Строка 98:
  
 
Пусть <tex> S = \{ i | e_i = u_1 u_{i + 1} \in EG\}, T = \{ i |f_i = u_i u_n \in EG\} </tex>.
 
Пусть <tex> S = \{ i | e_i = u_1 u_{i + 1} \in EG\}, T = \{ i |f_i = u_i u_n \in EG\} </tex>.
[[Файл: Hvatal_3.png|400px|thumb|center|Множество <tex> S </tex> обозначено красным цветом, множество <tex> T </tex> обозначено синим цветом]]
+
[[Файл: Hvatal_3.png|330px|thumb|center|Множество <tex> S </tex> обозначено красным цветом, множество <tex> T </tex> обозначено синим цветом]]
  
 
{{Утверждение
 
{{Утверждение
Строка 105: Строка 105:
 
|proof=
 
|proof=
 
Пусть <tex> j \in S \cap T </tex>. Тогда получим гамильтонов цикл графа <tex> G </tex>:  <tex> 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 </tex>, что противоречит условию, что граф негамильтонов.
 
Пусть <tex> j \in S \cap T </tex>. Тогда получим гамильтонов цикл графа <tex> G </tex>:  <tex> 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 </tex>, что противоречит условию, что граф негамильтонов.
[[Файл: Hvatal_4.png|400px|thumb|center|]]
+
[[Файл: Hvatal_4.png|270px|thumb|center|]]
 
Значит, <tex> S \cap T </tex>, q.e.d.
 
Значит, <tex> S \cap T </tex>, q.e.d.
 
}}
 
}}

Версия 10:35, 24 апреля 2012

Определение:
Пусть неориентированный граф [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]

См. также

Литература

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