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

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

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

Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
Текущая версия Ваш текст
Строка 31: Строка 31:
 
* <tex> d_1 \leqslant d_2 \leqslant \ldots \leqslant d_n </tex> — его последовательность степеней.
 
* <tex> d_1 \leqslant d_2 \leqslant \ldots \leqslant 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 \leqslant k < n/2 \rightarrow d_{n - k} \geqslant 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> [[Гамильтоновы_графы#.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|гамильтонов]].
 
|proof=
 
|proof=
Строка 39: Строка 39:
 
1
 
1
 
|statement=
 
|statement=
<tex> d_k \leqslant k \Leftrightarrow |\{ v \in VG \mid d_v \leqslant k \}| \geqslant k. </tex>
+
<tex> d_k \leqslant k \Leftrightarrow |\{ v \in VG | d_v \leqslant k \}| \geqslant 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 \leqslant d_2 \leqslant \ldots \leqslant d_k </tex>,
 
* <tex> d_k \leqslant k </tex>,
 
* <tex> d_k \leqslant 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 \leqslant k \} \Rightarrow |\{ v \in VG | d_v \leqslant k \}| \geqslant k </tex>.
  
<tex> \Leftarrow </tex> Из условия:
+
"<tex> \Leftarrow </tex>" Пусть:
* <tex> |\{ v \in VG \mid d_v \leqslant k \}| = k + p </tex>,
+
* <tex> |\{ v \in VG | d_v \leqslant k \}| = k + p </tex>,
 
* <tex> p \geqslant 0 </tex>.
 
* <tex> p \geqslant 0 </tex>.
 
Расположим вершины в неубывающем порядке их степеней. <br>
 
Расположим вершины в неубывающем порядке их степеней. <br>
Строка 58: Строка 58:
 
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} \geqslant n - k \Leftrightarrow |\{ v \in VG | d_v \geqslant n - k \}| \geqslant k + 1. </tex>
 
|proof=
 
|proof=
<tex> \Rightarrow </tex> Пусть:
+
"<tex> \Rightarrow </tex>" Пусть:
 
* <tex> d_{n - k} \geqslant n - k </tex>,
 
* <tex> d_{n - k} \geqslant n - k </tex>,
 
* <tex> d_{n - k} \leqslant d_{n - k + 1} \leqslant \ldots \leqslant d_n </tex>,  
 
* <tex> d_{n - k} \leqslant d_{n - k + 1} \leqslant \ldots \leqslant 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 \geqslant n - k \} \Rightarrow \{ v \in VG | d_v \geqslant n - k \} \geqslant k + 1 </tex>.
  
<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 \geqslant n - k \}| = k + 1 + p, (p \geqslant 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 \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>.   
Строка 78: Строка 78:
 
Если импликация <tex> (*) </tex> верна для некоторой последовательности степеней <tex> d </tex>, то она верна и для неубывающей последовательности <tex> d' </tex>, мажорирующей <tex> d </tex>.
 
Если импликация <tex> (*) </tex> верна для некоторой последовательности степеней <tex> d </tex>, то она верна и для неубывающей последовательности <tex> d' </tex>, мажорирующей <tex> d </tex>.
 
|proof=
 
|proof=
# Если <tex> d'_k > k </tex>, то первый аргумент импликации всегда ложен, следовательно импликация верна вне зависимости от второго аргумента. Значит, в этом случае импликация <tex> (*) </tex> верна для последовательности <tex> d' </tex>.
+
# Пусть <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> 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> (*) </tex> выполняется и для последовательности <tex> d' </tex>.
 
}}
 
}}
Строка 97: Строка 97:
 
Отбрасывая ребро <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> обозначено синим цветом]]
 
[[Файл: Hvatal_3.png|330px|thumb|center|Множество <tex> S </tex> обозначено красным цветом, множество <tex> T </tex> обозначено синим цветом]]
  
Строка 104: Строка 104:
 
<tex> S \cap T  = \emptyset </tex>.
 
<tex> S \cap T  = \emptyset </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 \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|270px|thumb|center|]]
 
[[Файл: Hvatal_4.png|270px|thumb|center|]]
 
Значит, <tex> S \cap T </tex>.
 
Значит, <tex> S \cap T </tex>.

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

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

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