Лемма о длине цикла
| Лемма (о длине цикла): |
Пусть [math]G[/math] - произвольный неориентированный граф и [math]\delta[/math] - минимальная степень его вершин. Если [math]\delta \ge 2[/math], то в графе [math]G[/math] существует цикл [math]C[/math] длиной [math]l \ge \delta + 1[/math]. |
| Доказательство: |
| [math]\triangleright[/math] |
|
Рассмотрим путь максимальной длины [math]P = v_0 v_1 .. v_s[/math]. Все смежные с [math]v_0[/math] вершины лежат на [math]P[/math]. Обозначим [math]k = max\{i: v_0 v_i \in E\}[/math]. Тогда [math]\delta \le deg\ v_0 \le k[/math]. Цикл [math]C = v_0 v_1 .. v_k v_0[/math] имеет длину [math]l = k + 1 \ge \delta + 1[/math] |
| [math]\triangleleft[/math] |
Теорема
| Теорема (Дирак): |
Пусть [math]G[/math] - неориентированный граф и [math]\delta[/math] - минимальная степень его вершин. Если [math]n \ge 3[/math] и [math]\delta \ge n/2[/math], то [math]G[/math] - гамильтонов граф. |
| Доказательство: |
| [math]\triangleright[/math] |
|
Пусть [math]C[/math] - цикл наибольшей длины в графе [math]G[/math]. По лемме его длина [math]l \ge \delta + 1[/math]. Если [math]C[/math] - гамильтонов, то теорема доказана. Предположим обратное, т. е. [math]G \backslash C \ne \varnothing[/math]. Рассмотрим путь [math]P = x..y : P \cap C = \{y\}[/math] наибольшей длины [math]m[/math]. Заметим, что по условию [math]\delta \ge n/2[/math], а значит [math]\delta \ge 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 \le m + (l - 2m)/2 =l/2 \lt n/2 \le \delta[/math]. Противоречие. |
| [math]\triangleleft[/math] |
Альтернативное доказательство
| Теорема (Дирак — альтернативное доказательство): |
Пусть [math]G[/math] - неориентированный граф и [math]\delta[/math] - минимальная степень его вершин. Если [math]n \ge 3[/math] и [math]\delta \ge n/2[/math], то [math]G[/math] - гамильтонов граф. |
| Доказательство: |
| [math]\triangleright[/math] |
|
Для [math]\forall k[/math] верна импликация [math]d_k \le k \lt n/2 \Rightarrow d_{n-k} \ge n-k[/math], поскольку левая её часть всегда ложна. Тогда по теореме Хватала [math]G[/math] - гамильтонов граф. |
| [math]\triangleleft[/math] |
См. также
Источники
Graham, R.L., Groetschel M., and Lovász L., eds. (1996). Handbook of Combinatorics, Volumes 1
