Редактирование: Теорема Хватала
Внимание! Вы не авторизовались на сайте. Ваш 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 \ | + | <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= | ||
Строка 41: | Строка 41: | ||
<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 \mid 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>, | ||
Строка 47: | Строка 47: | ||
<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 \mid d_v \leqslant k \} \Rightarrow |\{ v \in VG \mid 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 \mid d_v \leqslant k \}| = k + p </tex>, | ||
* <tex> p \geqslant 0 </tex>. | * <tex> p \geqslant 0 </tex>. | ||
Строка 60: | Строка 60: | ||
<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 \mid 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>, | ||
Строка 66: | Строка 66: | ||
<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 \mid d_v \geqslant n - k \} \Rightarrow \{ v \in VG \mid 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 \mid d_v \geqslant n - k \}| = k + 1 + p, (p \geqslant 0)</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 \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>. | ||
}} | }} | ||
Строка 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>, что противоречит условию, что граф негамильтонов. | |
[[Файл: Hvatal_4.png|270px|thumb|center|]] | [[Файл: Hvatal_4.png|270px|thumb|center|]] | ||
Значит, <tex> S \cap T </tex>. | Значит, <tex> S \cap T </tex>. |