Материал из Викиконспекты
|
|
Строка 47: |
Строка 47: |
| | | |
| == Источники == | | == Источники == |
| + | * [[wikipedia:en:Dirac's_Theorem|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. | | * 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. |
− | * [[wikipedia:en:Dirac's_Theorem|Wikipedia {{---}} Dirac's Theorem]]
| + | |
| | | |
| [[Категория: Алгоритмы и структуры данных]] | | [[Категория: Алгоритмы и структуры данных]] |
| [[Категория: Обходы графов]] | | [[Категория: Обходы графов]] |
Версия 22:55, 11 октября 2014
Лемма о длине цикла
Лемма (о длине цикла): |
Пусть [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] |
Теорема
Теорема (Дирак): |
Пусть [math]G[/math] — неориентированный граф и [math]\delta[/math] — минимальная степень его вершин. Если [math]n \geqslant 3[/math] и [math]\delta \geqslant n/2[/math], то [math]G[/math] — гамильтонов граф. |
Доказательство: |
[math]\triangleright[/math] |
Пусть [math]C[/math] - цикл наибольшей длины в графе [math]G[/math]. По лемме его длина [math]l \geqslant \delta + 1[/math]. Если [math]C[/math] - гамильтонов, то теорема доказана. Предположим обратное, т. е. [math]G \backslash C \ne \varnothing[/math]. Рассмотрим путь [math]P = x \dots y : P \cap C = \{y\}[/math] наибольшей длины [math]m[/math]. Заметим, что по условию [math]\delta \geqslant n/2[/math], а значит [math]\delta \geqslant n - \delta \gt n - l = |V(G \backslash C)|[/math] и каждая вершина из [math]G \backslash C[/math] смежна с некоторыми вершинами из [math]C[/math].
Заметим, что вершина [math]x[/math] не может быть смежна:
- с вершинами из [math]C[/math], расстояние от которых до [math]y[/math] (по [math]C[/math]) не превышает m. Действительно, пусть вершина [math]v \in C[/math] и расстояние от [math]v[/math] до [math]y[/math] по циклу меньше либо равно [math]m[/math]. Тогда этот участок цикла можно заменить на [math]v \rightarrow x \rightarrow P \rightarrow y[/math], длина которого [math]m + 1[/math]. Таким образом образуется цикл большей длины, что противоречит предположению о максимальности цикл [math]C[/math].
- двум смежным вершинам на [math]C[/math]. Пусть [math]u, v \in C[/math] и [math]\{(u, v), (u, x), (x, v)\} \in E[/math]. Тогда заменив ребро [math](u, v)[/math] на [math]u \rightarrow x \rightarrow v[/math], увеличим длину цикла на [math]1[/math].
- вершинам из [math]G \backslash (C \cup P)[/math], поскольку [math]P[/math] максимальный.
Получаем [math]deg\ x \leqslant m + (l - 2m)/2 = l/2 \lt n/2 \leqslant \delta[/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]\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.