Материал из Викиконспекты
|
(Метки: правка с мобильного устройства, правка из мобильной версии) |
| Строка 7: |
Строка 7: |
| | }} | | }} |
| | | | |
| − | ==Теорема==
| + | 8м топ АУФ! |
| − | | |
| − | {{Теорема
| |
| − | |about=Дирак
| |
| − | |statement=
| |
| − | Пусть <tex>G</tex> {{---}} неориентированный граф и <tex>\delta</tex> {{---}} минимальная степень его вершин. Если <tex>n \geqslant 3</tex> и <tex>\delta \geqslant n/2</tex>, то <tex>G</tex> {{---}} [[Гамильтоновы графы|гамильтонов граф]].
| |
| − | |proof=
| |
| − | Пусть <tex>C</tex> {{---}} цикл наибольшей длины в графе <tex>G</tex>. По лемме его длина <tex>l \geqslant \delta + 1</tex>. Если <tex>C</tex> - гамильтонов, то теорема доказана. Предположим обратное, т. е. <tex>G \backslash C \ne \varnothing</tex>. Рассмотрим путь <tex>P = x \dots y : P \cap C = \{y\}</tex> наибольшей длины <tex>m</tex>. Заметим, что по условию <tex>\delta \geqslant n/2</tex>, а значит <tex>\delta \geqslant n - \delta > n - l = |V(G \backslash C)|</tex>. Поэтому каждая вершина из <tex>G \backslash C</tex> смежна с некоторыми вершинами из <tex>C</tex>.
| |
| − | Заметим, что вершина <tex>x</tex> не может быть смежна:
| |
| − | * с вершинами из <tex>C</tex>, расстояние от которых до <tex>y</tex> (по <tex>C</tex>) не превышает m. Действительно, пусть вершина <tex>v \in C</tex> и расстояние от <tex>v</tex> до <tex>y</tex> по циклу меньше либо равно <tex>m</tex>. Тогда этот участок цикла можно заменить на <tex>v \rightarrow x \rightarrow P \rightarrow y</tex>, длина которого <tex>m + 1</tex>. Таким образом образуется цикл большей длины, что противоречит предположению о максимальности цикл <tex>C</tex>.
| |
| − | * двум смежным вершинам на <tex>C</tex>. Пусть <tex>u, v \in C</tex> и <tex>\{(u, v), (u, x), (x, v)\} \in E</tex>. Тогда заменив ребро <tex>(u, v)</tex> на <tex>u \rightarrow x \rightarrow v</tex>, увеличим длину цикла на <tex>1</tex>.
| |
| − | * вершинам из <tex>G \backslash (C \cup P)</tex>, поскольку <tex>P</tex> максимальный.
| |
| − | | |
| − | Получаем <tex>deg\ x \leqslant m + (l - 2m)/2 = l/2 < n/2 \leqslant \delta</tex>. Противоречие.
| |
| − | }}
| |
| | | | |
| | ==Альтернативное доказательство== | | ==Альтернативное доказательство== |
Версия 16:15, 10 марта 2021
Лемма о длине цикла
| Лемма (о длине цикла): |
Пусть [math]G[/math] — произвольный неориентированный граф и [math]\delta[/math] — минимальная степень его вершин. Если [math]\delta \geqslant 2[/math], то в графе [math]G[/math] существует цикл [math]C[/math] длиной [math]l \geqslant \delta + 1[/math]. |
| Доказательство: |
| [math]\triangleright[/math] |
|
Рассмотрим путь максимальной длины [math]P = v_0 v_1 \dots v_s[/math]. Все смежные с [math]v_0[/math] вершины лежат на [math]P[/math]. Обозначим [math]k = \max \{i: v_0 v_i \in E\} [/math]. Тогда [math]\delta \leqslant \deg v_0 \leqslant k[/math]. Цикл [math]C = v_0 v_1 \dots v_k v_0[/math] имеет длину [math]l = k + 1 \geqslant \delta + 1[/math] |
| [math]\triangleleft[/math] |
8м топ АУФ!
Альтернативное доказательство
| Теорема (Дирак — альтернативное доказательство): |
Пусть [math]G[/math] — неориентированный граф и [math]\delta[/math] — минимальная степень его вершин. Если [math]n \geqslant 3[/math] и [math]\delta \geqslant n/2[/math], то [math]G[/math] — гамильтонов граф. |
| Доказательство: |
| [math]\triangleright[/math] |
|
Для [math]\forall k[/math] верна импликация [math]d_k \leqslant k \lt n/2 \Rightarrow d_{n-k} \geqslant n-k[/math], поскольку левая её часть всегда ложна. Тогда по теореме Хватала [math]G[/math] — гамильтонов граф. |
| [math]\triangleleft[/math] |
| Теорема (Вывод из теоремы Оре): |
Пусть [math]G[/math] — неориентированный граф и [math]\delta[/math] — минимальная степень его вершин. Если [math]n \geqslant 3[/math] и [math]\delta \geqslant n/2[/math], то [math]G[/math] — гамильтонов граф. |
| Доказательство: |
| [math]\triangleright[/math] |
|
Возьмем любые неравные вершины [math] u, v \in G [/math]. Тогда [math] \displaystyle \deg u + \deg v \geqslant \frac n 2 + \frac n 2 = n [/math]. По теореме Оре [math] G [/math] — гамильтонов граф. |
| [math]\triangleleft[/math] |
См. также
Источники информации
- Wikipedia — Dirac's Theorem
- Graham, R.L., Groetschel M., and Lovász L., eds. (1996). Handbook of Combinatorics, Volumes 1 and 2. Elsevier (North-Holland), Amsterdam, and MIT Press, Cambridge, Mass. ISBN 0-262-07169-X.
