Редактирование: Теорема Хватала

Перейти к: навигация, поиск

Внимание! Вы не авторизовались на сайте. Ваш IP-адрес будет публично видимым, если вы будете вносить любые правки. Если вы войдёте или создадите учётную запись, правки вместо этого будут связаны с вашим именем пользователя, а также у вас появятся другие преимущества.

Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
Текущая версия Ваш текст
Строка 1: Строка 1:
 
{{Определение
 
{{Определение
 
|definition=
 
|definition=
Пусть [[Основные_определения_теории_графов#.D0.9D.D0.B5.D0.BE.D1.80.D0.B8.D0.B5.D0.BD.D1.82.D0.B8.D1.80.D0.BE.D0.B2.D0.B0.D0.BD.D0.BD.D1.8B.D0.B5_.D0.B3.D1.80.D0.B0.D1.84.D1.8B|неориентированный граф]] <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 \leqslant d_2 \leqslant \ldots \leqslant d_n </tex>. Последовательность <tex> d_1, d_2, \ldots, d_n </tex> называют '''последовательностью степеней''' графа <tex> G </tex>.
+
Пусть [[Основные_определения_теории_графов|неориентированный граф]] <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>.
 
}}
 
}}
  
Строка 8: Строка 8:
 
О добавлении ребра в граф
 
О добавлении ребра в граф
 
|statement=
 
|statement=
Пусть неориентированный граф <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> 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> на положенное место, то исходная последовательность будет мажорироваться полученной.
[[Файл: Hvatal_1.png|270px|thumb|center|Исходная последовательность степеней <tex> d </tex>]]
 
 
 
* Рассмотрим элементы с номерами <tex> s = \overline{1, i - 1} </tex>. Они не изменились, следовательно мажорируются собой.
 
* Рассмотрим элементы с номерами <tex> s = \overline{i, j - 1} </tex>. <tex> s </tex>-й элемент полученной последовательности равен <tex> s + 1 </tex>-му элементу исходной. <tex> d_s \leqslant d_{s + 1} \Rightarrow d_s \leqslant d'_s = d_{s + 1} </tex>.
 
* Расмотрим <tex>j</tex>-ый элемент. Имеем <tex>d'_j \ge d'_{j-1} = d_{j} </tex>.
 
* Рассмотрим элементы с номерами <tex> s = \overline{j + 1, n} </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.
 
}}
 
}}
  
Строка 27: Строка 20:
 
|statement=
 
|statement=
 
Пусть:
 
Пусть:
* <tex> G </tex> — [[Отношение_связности,_компоненты_связности#.D0.A1.D0.BB.D1.83.D1.87.D0.B0.D0.B9_.D0.BD.D0.B5.D0.BE.D1.80.D0.B8.D0.B5.D0.BD.D1.82.D0.B8.D1.80.D0.BE.D0.B2.D0.B0.D0.BD.D0.BD.D0.BE.D0.B3.D0.BE_.D0.B3.D1.80.D0.B0.D1.84.D0.B0|связный граф]],
+
* <tex> G </tex> — [[Отношение связности, компоненты связности|связный граф]],
* <tex> n = |VG| \geqslant 3 </tex> — количество вершин,
+
* <tex> n = |VG| \geq 3 </tex> — количество вершин,
* <tex> d_1 \leqslant d_2 \leqslant \ldots \leqslant d_n </tex> — его последовательность степеней.
+
* <tex> d_1 \leq d_2 \leq \ldots \leq d_n </tex> — его последовательность степеней.
 
Тогда если <tex> \forall k \in \mathbb N </tex> верна импликация: <br>
 
Тогда если <tex> \forall k \in \mathbb N </tex> верна импликация: <br>
<center><tex> d_k \leqslant k < n/2 \Rightarrow d_{n - k} \geqslant n - k, (*) </tex></center>
+
<center><tex> d_k \leq k < n/2 \rightarrow d_{n - k} \geq n - k, (*) </tex></center>
то граф <tex> G </tex> [[Гамильтоновы_графы#.D0.9E.D1.81.D0.BD.D0.BE.D0.B2.D0.BD.D1.8B.D0.B5_.D0.BE.D0.BF.D1.80.D0.B5.D0.B4.D0.B5.D0.BB.D0.B5.D0.BD.D0.B8.D1.8F|гамильтонов]].
+
то граф <tex> G </tex> [[Гамильтоновы графы|гамильтонов]].
 
|proof=
 
|proof=
 
Для доказательства теоремы, докажем 3 леммы.
 
Для доказательства теоремы, докажем 3 леммы.
Строка 39: Строка 32:
 
1
 
1
 
|statement=
 
|statement=
<tex> d_k \leqslant k \Leftrightarrow |\{ v \in VG \mid d_v \leqslant k \}| \geqslant k. </tex>
+
<tex> d_k \leq k \Leftrightarrow |\{ v \in VG | d_v \leq k \}| \geq k. </tex>
 
|proof=
 
|proof=
<tex> \Rightarrow </tex> Пусть:
+
"<tex> \Rightarrow </tex>" Пусть:
* <tex> d_1 \leqslant d_2 \leqslant \ldots \leqslant d_k </tex>,
+
* <tex> d_1 \leq d_2 \leq \ldots \leq d_k </tex>,
* <tex> d_k \leqslant k </tex>,
+
* <tex> d_k \leq k </tex>,
 
* <tex> |\{ d_1, d_2, \ldots, d_k \}| = k </tex>.
 
* <tex> |\{ d_1, d_2, \ldots, d_k \}| = k </tex>.
<tex> \{ d_1, d_2, \ldots, d_k \} \subseteq \{ v \in VG \mid d_v \leqslant k \} \Rightarrow |\{ v \in VG \mid d_v \leqslant k \}| \geqslant k </tex>.
+
<tex> \{ 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 </tex>, q.e.d.
  
<tex> \Leftarrow </tex> Из условия:
+
"<tex> \Leftarrow </tex>" Пусть:
* <tex> |\{ v \in VG \mid d_v \leqslant k \}| = k + p </tex>,
+
* <tex> |\{ v \in VG | d_v \leq k \}| = k + p </tex>,
* <tex> p \geqslant 0 </tex>.
+
* <tex> p \geq 0 </tex>.
 
Расположим вершины в неубывающем порядке их степеней. <br>
 
Расположим вершины в неубывающем порядке их степеней. <br>
<tex> d_1 \leqslant d_2 \leqslant \ldots \leqslant d_k \leqslant \ldots \leqslant d_{k + p} \leqslant k \Rightarrow d_k \leqslant k </tex>.
+
<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.
 
}}
 
}}
  
Строка 58: Строка 51:
 
2
 
2
 
|statement=
 
|statement=
<tex>\ d_{n - k} \geqslant n - k \Leftrightarrow |\{ v \in VG \mid d_v \geqslant n - k \}| \geqslant k + 1. </tex>
+
<tex>\ d_{n - k} \geq n - k \Leftrightarrow |\{ v \in VG | d_v \geq n - k \}| \geq k + 1. </tex>
 
|proof=
 
|proof=
<tex> \Rightarrow </tex> Пусть:
+
"<tex> \Rightarrow </tex>" Пусть:
* <tex> d_{n - k} \geqslant n - k </tex>,
+
* <tex> d_{n - k} \geq n - k </tex>,
* <tex> d_{n - k} \leqslant d_{n - k + 1} \leqslant \ldots \leqslant d_n </tex>,  
+
* <tex> d_{n - k} \leq d_{n - k + 1} \leq \ldots \leq d_n </tex>,  
 
* <tex> |\{ d_{n - k}, d_{n - k + 1}, \ldots , d_n \}| = k + 1 </tex>.
 
* <tex> |\{ d_{n - k}, d_{n - k + 1}, \ldots , d_n \}| = k + 1 </tex>.
<tex> \{ d_{n - k}, d_{n - k + 1}, \ldots , d_n \} \subseteq \{ v \in VG \mid d_v \geqslant n - k \} \Rightarrow \{ v \in VG \mid d_v \geqslant n - k \} \geqslant k + 1 </tex>.
+
<tex> \{ 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 </tex>, q.e.d.
  
<tex> \Leftarrow </tex>:
+
"<tex> \Leftarrow </tex>" Пусть:
* <tex> |\{ v \in VG \mid d_v \geqslant n - k \}| = k + 1 + p, (p \geqslant 0)</tex>,
+
* <tex> |\{ v \in VG | d_v \geq n - k \}| = k + 1 + p </tex>,
 +
* <tex> p \geq 0 </tex>.
 
Расположим вершины в неубывающем порядке их степеней.
 
Расположим вершины в неубывающем порядке их степеней.
<tex> d_n \geqslant d_{n - 1} \ldots \geqslant d_{n - k} \geqslant \ldots \geqslant d_{n - k - p} \geqslant n - k \Rightarrow d_{n - k} \geqslant n - k </tex>.   
+
<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.   
 
}}
 
}}
  
Строка 77: Строка 71:
 
|statement=
 
|statement=
 
Если импликация <tex> (*) </tex> верна для некоторой последовательности степеней <tex> d </tex>, то она верна и для неубывающей последовательности <tex> d' </tex>, мажорирующей <tex> d </tex>.
 
Если импликация <tex> (*) </tex> верна для некоторой последовательности степеней <tex> d </tex>, то она верна и для неубывающей последовательности <tex> d' </tex>, мажорирующей <tex> d </tex>.
|proof=
 
# Если <tex> d'_k > k </tex>, то первый аргумент импликации всегда ложен, следовательно импликация верна вне зависимости от второго аргумента. Значит, в этом случае импликация <tex> (*) </tex> верна для последовательности <tex> d' </tex>.
 
# Если <tex> d'_k \leqslant k, \mbox{ } d'_{n - k} \geqslant d_{n - k} \geqslant n - k </tex>, то оба аргумента импликации всегда истинны. Значит, и в этом случае импликация <tex> (*) </tex> верна для последовательности <tex> d' </tex>.
 
Значит, импликация <tex> (*) </tex> выполняется и для последовательности <tex> d' </tex>.
 
 
}}
 
}}
  
 
Приведем доказательство от противного.
 
Приведем доказательство от противного.
  
Пусть существует граф с числом вершин <tex> n \geqslant 3 </tex>, удовлетворяющий <tex> (*) </tex>, но негамильтонов.
+
Пусть существует граф с числом вершин <tex> n \geq 3 </tex>, удовлетворяющий <tex> (*) </tex>, но негамильтонов.
Будем добавлять в него ребра до тех пор, пока не получим максимально возможный негамильтонов граф <tex> G </tex> (то есть добавление еще одного ребра сделает граф <tex> G </tex> гамильтоновым).  
+
Будем добавлять в него [[Основные определения теории графов|рёбра]] до тех пор, пока не получим максимально возможный негамильтонов граф <tex> G </tex> (то есть добавление еще одного ребра сделает граф <tex> G </tex> гамильтоновым).  
 
По лемме о добавлении ребра и лемме №3 импликация <tex> (*) </tex> остается верной для графа <tex> G </tex>.
 
По лемме о добавлении ребра и лемме №3 импликация <tex> (*) </tex> остается верной для графа <tex> G </tex>.
Очевидно, что граф <tex>\ K_n </tex> гамильтонов при <tex> k \geqslant 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> u </tex> и <tex> v </tex> графа <tex> G </tex>, такие что <tex> \deg u + \deg v </tex> — максимально.
Будем считать, что <tex> \deg u \leqslant \deg v </tex>.
+
Будем считать, что <tex> \deg u \leq \deg v </tex>.
 
Добавив к <tex> G </tex> новое ребро <tex> e = uv </tex>, получим гамильтонов граф <tex> G + e </tex>.
 
Добавив к <tex> G </tex> новое ребро <tex> e = uv </tex>, получим гамильтонов граф <tex> G + e </tex>.
Рассмотрим гамильтонов цикл графа <tex> G + e </tex>: в нём обязательно присутствует ребро <tex> e </tex>.
+
Рассмотрим [[Гамильтоновы графы|гамильтонов цикл]] графа <tex> G + e </tex>: в нём обязательно присутствует ребро <tex> e </tex>.
 
Отбрасывая ребро <tex> e </tex>, получим гамильтонову <tex> (u, v) </tex>-цепь в графе <tex> G </tex>: <tex> u = u_1 \rightarrow u_2 \rightarrow \ldots \rightarrow u_n = v </tex>.
 
Отбрасывая ребро <tex> e </tex>, получим гамильтонову <tex> (u, v) </tex>-цепь в графе <tex> G </tex>: <tex> u = u_1 \rightarrow u_2 \rightarrow \ldots \rightarrow u_n = v </tex>.
  
Пусть <tex> S = \{ i \mid e_i = u_1 u_{i + 1} \in EG\}, T = \{ i \mid 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|330px|thumb|center|Множество <tex> S </tex> обозначено красным цветом, множество <tex> T </tex> обозначено синим цветом]]
 
  
{{Утверждение
+
{{Лемма
 
|statement=
 
|statement=
<tex> S \cap T  = \emptyset </tex>.
+
<tex> S \cap T  = \varnothing </tex>, иначе в графе <tex> G </tex> есть гамильтонов цикл.
 
|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 \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 </tex>, что противоречит условию, что граф негамильтонов. Значит, <tex> S \cap T </tex>, q.e.d.
[[Файл: Hvatal_4.png|270px|thumb|center|]]
 
Значит, <tex> S \cap T </tex>.
 
 
}}
 
}}
  
Из определений <tex> S </tex> и <tex> T </tex> следует, что <tex> S \cup T \subseteq \{1, 2, ..., n - 1 \} \Rightarrow 2 \deg u \leqslant \deg u + \deg v = |S| + |T| = |S \cup T| < n </tex>. Значит, <tex> \deg u < n/2 </tex>.
+
Из определений <tex> S </tex> и <tex> T </tex> следует, что <tex> S \cup T \subseteq \{1, 2, ..., n - 1 \} </tex>, поэтому <tex> 2 \deg u \leq \deg u + \deg v = |S| + |T| = |S \cup T| < n </tex>, то есть <tex> \deg u < n/2 </tex>.
  
Так как <tex> S \cap T  = \emptyset </tex>, ни одна вершина <tex> u_j </tex> не смежна с <tex> v = u_n </tex> (для <tex> j \in S </tex>). В силу выбора <tex> u </tex> и <tex> v </tex>, получим, что <tex> \deg u_j \leqslant \deg u </tex>. Пусть <tex> k = \deg u = |S| </tex>. Значит, <tex> \exists k </tex> вершин, степень которых не превосходит <tex> k </tex>.
+
Так как <tex> S \cap T  = \varnothing </tex>, ни одна вершина <tex> u_j </tex> не смежна с <tex> v = u_n </tex> (для <tex> j \in S </tex>). В силу выбора <tex> u </tex> и <tex> v </tex>, получим, что <tex> \deg u_j \leq \deg u </tex>. Положим, что <tex> k = \deg u </tex>.
 +
Тогда имеется по крайней мере <tex> |S| = \deg u = k </tex> вершин, степень которых не превосходит k.
  
По лемме №1: <tex> d_k \leqslant k < n/2 </tex>. В силу импликации <tex> (*) </tex>: <tex> d_{n - k} \geqslant  n - k </tex>.
+
По лемме №1, выполняется: <tex> d_k \leq k < n/2 </tex>.
  
По лемме №2, <tex> \exists k + 1 </tex> вершин, степень которых не меньше <tex> n - k </tex>.
+
Исходя из <tex> (*) </tex>, получаем: <tex> d_{n - k} \geq n - k </tex>.
  
Так как <tex> k = \deg u </tex>, то вершина <tex> u </tex> может быть смежна максимум с <tex> k </tex> из этих <tex> k+1 </tex> вершин. Значит, существует вершина <tex> w </tex>, не являющаяся смежной с <tex> u </tex> и для которой <tex> \deg w \geqslant n - k </tex>. Тогда получим, что <tex> \deg u + \deg w \geqslant k + (n - k) = n > \deg u + \deg v </tex>, что противоречит выбору <tex> u </tex> и <tex> v </tex>.
+
По лемме №2, имеется по крайней мере <tex> k + 1 </tex> вершин, степень которых не меньше <tex> n - k </tex>.
  
Значит, предположение неверно.
+
Так как <tex> k = \deg u </tex>, то вершина <tex> u </tex> может быть смежна максимум с <tex> k </tex> из этих <tex> k+1 </tex> вершин. Значит, существует вершина <tex> w </tex>, не являющаяся смежной с <tex> u </tex> и для которой <tex> \deg w \geq n - k </tex>. Тогда получим, что <tex> \deg u + \deg w \geq k + (n - k) = n > \deg u + \deg v </tex>, что противоречит выбору <tex> u </tex> и <tex> v </tex>.
 +
 
 +
Значит, предположение неверно, q.e.d.
 
}}
 
}}
  
==См. также==
+
==Литература==
* [[Гамильтоновы графы]]
 
* [[Теорема Дирака]]
 
* [[Теорема Оре]]
 
 
 
== Источники информации ==
 
 
* Асанов М., Баранский В., Расин В.: ''Дискретная математика: Графы, матроиды, алгоритмы''
 
* Асанов М., Баранский В., Расин В.: ''Дискретная математика: Графы, матроиды, алгоритмы''
  
 
[[Категория: Алгоритмы и структуры данных]]
 
[[Категория: Алгоритмы и структуры данных]]
 
[[Категория: Обходы графов]]
 
[[Категория: Обходы графов]]
[[Категория: Гамильтоновы графы]]
 

Пожалуйста, учтите, что любой ваш вклад в проект «Викиконспекты» может быть отредактирован или удалён другими участниками. Если вы не хотите, чтобы кто-либо изменял ваши тексты, не помещайте их сюда.
Вы также подтверждаете, что являетесь автором вносимых дополнений, или скопировали их из источника, допускающего свободное распространение и изменение своего содержимого (см. Викиконспекты:Авторские права). НЕ РАЗМЕЩАЙТЕ БЕЗ РАЗРЕШЕНИЯ ОХРАНЯЕМЫЕ АВТОРСКИМ ПРАВОМ МАТЕРИАЛЫ!

Чтобы изменить эту страницу, пожалуйста, ответьте на приведённый ниже вопрос (подробнее):

Отменить | Справка по редактированию (в новом окне)