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

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 1: Строка 1:
 +
{{Определение
 +
|definition=
 +
Пусть [[Основные_определения_теории_графов|неориентированный граф]] <tex> G </tex> имеет <tex> n </tex> вершин: <tex> v_1, v_2, \ldots, v_n </tex>. Пусть <tex> d_i = \deg v_i \mbox{ } (i = \overline{1, n}) </tex> и вершины графа упорядочены таким образом, что <tex> d_1 \leq d_2 \leq \ldots \leq d_n </tex>. Последовательность <tex> d_1, d_2, \ldots, d_n </tex> называют '''последовательностью степеней''' графа <tex> G </tex>.
 +
}}
 +
 +
{{Лемма
 +
|about=
 +
О добавлении ребра в граф
 +
|statement=
 +
Пусть [[Основные_определения_теории_графов|неориентированный граф]] <tex> G' </tex> получен из неориентированного графа <tex> G </tex> добавлением одного нового ребра <tex> e </tex>. Тогда последовательность степеней графа <tex> G </tex> мажорируется последовательностью степеней графа <tex> G' </tex>.
 +
|proof=
 +
''Замечание'': Если в неубывающей последовательности <tex> d_1, d_2, \ldots, d_n </tex> увеличить на единицу число <tex> d_i </tex>, а затем привести последовательность к неубывающему виду, переставив число <tex> d_i + 1 </tex> на положенное место, то исходная последовательность будет мажорироваться полученной.
 +
При добавлении в граф ребра <tex> e = uv, \mbox{ } (u \neq v) </tex>, степени вершин <tex> u </tex> и <tex> v </tex> увеличатся на единицу. Для доказательства леммы, дважды воспользуемся замечанием.
 +
}}
 +
 
{{Теорема
 
{{Теорема
 
|about=
 
|about=
Строка 57: Строка 72:
 
}}
 
}}
  
Приведем доказательство от противного. <br>
+
Приведем доказательство от противного.
Пусть теорема Хватала не верна, тогда существует граф с числом вершин <tex> n \geq 3 </tex>, удовлетворяющий <tex> (*) </tex>, но негамильтонов.
+
 
 +
Пусть существует граф с числом вершин <tex> n \geq 3 </tex>, удовлетворяющий <tex> (*) </tex>, но негамильтонов.
 
Будем добавлять в него [[Основные определения теории графов|рёбра]] до тех пор, пока не получим максимально возможный негамильтонов граф <tex> G </tex> (то есть добавление еще одного ребра сделает граф <tex> G </tex> гамильтоновым).  
 
Будем добавлять в него [[Основные определения теории графов|рёбра]] до тех пор, пока не получим максимально возможный негамильтонов граф <tex> G </tex> (то есть добавление еще одного ребра сделает граф <tex> G </tex> гамильтоновым).  
Важно то, что добавление рёбер не нарушает <tex> (*) </tex>.
+
По лемме о добавлении ребра и лемме №3 импликация <tex> (*) </tex> остается верной для графа <tex> G </tex>.
Очевидно, что граф <tex>\ K_n </tex> гамильтонов для <tex>\ k \ge 3 </tex>.
+
Очевидно, что граф <tex>\ K_n </tex> гамильтонов при <tex> k \geq 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>\deg u \le \deg v </tex>.
+
Выберем две несмежные вершины <tex> u </tex> и <tex> v </tex> графа <tex> G </tex>, такие что <tex> \deg u + \deg v </tex> — максимально.
Добавив к <tex> G </tex> новое ребро <tex> e = uv </tex>, получим гамильтонов граф <tex> G + e</tex>.
+
Будем считать, что <tex> \deg u \leq \deg v </tex>.
Рассмотрим [[Гамильтоновы графы|гамильтонов цикл]] графа <tex> G + e</tex>: в нём обязательно присутствует ребро <tex> e </tex>. <br>
+
Добавив к <tex> G </tex> новое ребро <tex> e = uv </tex>, получим гамильтонов граф <tex> G + e </tex>.
Отбрасывая ребро <tex> e </tex>, получим гамильтонову (<tex>u</tex>, <tex>v</tex>)-цепь в графе <tex> G </tex>: <tex> u = u_1 - u_2 - ... - u_n = v </tex>. <br>
+
Рассмотрим [[Гамильтоновы графы|гамильтонов цикл]] графа <tex> G + e </tex>: в нём обязательно присутствует ребро <tex> e </tex>.
 +
Отбрасывая ребро <tex> e </tex>, получим гамильтонову (<tex> u, v </tex>)-цепь в графе <tex> G </tex>: <tex> u = u_1 - u_2 - ... - u_n = v </tex>. <br>
 
Пусть <tex>\ S = \{i|e_i = u_1 u_{i+1} \in E(G)\} </tex>. <br>
 
Пусть <tex>\ S = \{i|e_i = u_1 u_{i+1} \in E(G)\} </tex>. <br>
 
Пусть <tex>\ T = \{i|f_i = u_i u_n \in E(G)\} </tex>. <br>  
 
Пусть <tex>\ T = \{i|f_i = u_i u_n \in E(G)\} </tex>. <br>  

Версия 05:39, 20 ноября 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] e = uv, \mbox{ } (u \neq v) [/math], степени вершин [math] u [/math] и [math] v [/math] увеличатся на единицу. Для доказательства леммы, дважды воспользуемся замечанием.
[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 \} \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 [/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 \} \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 [/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] 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 - 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]

Литература

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