Теорема Дирака
Версия от 06:29, 21 ноября 2011; 192.168.0.2 (обсуждение)
Лемма (о длине цикла): |
Пусть - произвольный неориентированный граф и - минимальная степень его вершин. Если , то в графе существует цикл длиной . |
Доказательство: |
Рассмотрим путь максимальной длины | . Все смежные с вершины лежат на . Обозначим . Тогда . Цикл имеет длину
Теорема (Дирак): |
Пусть - неориентированный граф и - минимальная степень его вершин. Если и , то - гамильтонов граф. |
Доказательство: |
Пусть Заметим, что вершина - цикл наибольшей длины в графе . По лемме его длина . Если - гамильтонов, то теорема доказана. Предположим обратное, т. е. . Рассмотрим путь наибольшей длины . Заметим, что по условию , а значит и каждая вершина из смежна с некоторыми вершинами из . не может быть смежна с вершинами из , расстояние от которых до (по ) не превышает m, а также двум смежным вершинам(это противоречило бы максимальности цикла ). Получаем . Противоречие. |
Заметим, что эта теорема является следствием из теоремы Хватала. Действительно, для верна импликация , поскольку левая её часть всегда ложна.
Источники
Graham, R.L., Groetschel M., and Lovász L., eds. (1996). Handbook of Combinatorics, Volumes 1