Теорема Дирака

Теорема Дирака — это утверждение в теории графов, устанавливающее достаточное условие для существования гамильтонова цикла в графе. Теорема была сформулирована и доказана британским физиком и математиком Полем Дираком в 1952 году. Она является одним из классических результатов в области экстремальной теории графов и находит применение в задачах маршрутизации, планирования и анализа сетей.

Формулировка

Пусть \( G = (V, E) \) — простой неориентированный граф с \( n \) вершинами, где \( n \ge 3 \). Если для каждой вершины \( v \in V \) её степень \( \deg(v) \) удовлетворяет неравенству:

\[ \deg(v) \ge \frac{n}{2}, \]

то граф \( G \) является гамильтоновым, то есть содержит цикл, проходящий через каждую вершину ровно один раз.

Условие \( n \ge 3 \) исключает тривиальные случаи (например, граф с одной или двумя вершинами, для которых понятие гамильтонова цикла не определено). Теорема гарантирует существование гамильтонова цикла, но не указывает способ его построения.

История

Теорема была опубликована Полем Дираком в 1952 году в статье «Some Theorems on Abstract Graphs» в журнале Proceedings of the London Mathematical Society. Дирак, известный прежде всего своими работами в квантовой механике (уравнение Дирака, предсказание позитрона), также внёс вклад в комбинаторику и теорию графов. Его результат стал одним из первых достаточных условий гамильтоновости, наряду с более ранней теоремой Оре (1960) и более общими критериями, такими как теорема Бонди — Хватала.

Доказательство (краткая схема)

Доказательство теоремы Дирака обычно проводится методом от противного и опирается на свойства максимальных путей в графе. Основные шаги:

1. Предположим, что граф \( G \) удовлетворяет условию \( \deg(v) \ge n/2 \), но не является гамильтоновым.
2. Добавим к графу рёбра до тех пор, пока он не станет «максимальным негамильтоновым» (то есть добавление любого нового ребра приводит к появлению гамильтонова цикла).
3. В таком графе существует путь \( P = v_1, v_2, \dots, v_n \), содержащий все вершины, но не являющийся циклом (гамильтонов путь).
4. Так как добавление ребра \( (v_1, v_n) \) создало бы цикл, это ребро отсутствует. Следовательно, \( \deg(v_1) + \deg(v_n) < n \) (иначе по лемме о гамильтоновом цикле в максимальном графе можно было бы построить цикл).
5. Но по условию \( \deg(v_1) \ge n/2 \) и \( \deg(v_n) \ge n/2 \), что даёт \( \deg(v_1) + \deg(v_n) \ge n \). Противоречие.

Таким образом, исходное предположение неверно, и граф является гамильтоновым.

Связь с другими теоремами

Теорема Дирака является частным случаем более общего результата — теоремы Оре (1960), которая утверждает, что если для любой пары несмежных вершин \( u \) и \( v \) выполняется \( \deg(u) + \deg(v) \ge n \), то граф гамильтонов. Условие Дирака сильнее: из него следует условие Оре, но не наоборот. Например, граф, состоящий из двух треугольников, соединённых одной вершиной, может удовлетворять условию Оре, но не условию Дирака.

Дальнейшим обобщением является теорема Бонди — Хватала (1976), которая вводит понятие замыкания графа и даёт необходимое и достаточное условие гамильтоновости.

Примеры и контрпримеры

Пример выполнения условия

Рассмотрим полный граф \( K_n \) с \( n \ge 3 \). Степень каждой вершины равна \( n-1 \), что заведомо больше \( n/2 \). Такой граф, очевидно, содержит гамильтоновы циклы.

Пример невыполнения условия

Граф, состоящий из двух полных подграфов \( K_{n/2} \), соединённых единственным ребром (при \( n \) чётном). Вершины, не принадлежащие этому ребру, имеют степень \( n/2 - 1 \), что меньше \( n/2 \). Такой граф не является гамильтоновым, так как для прохода между компонентами требуется использовать единственное ребро, что невозможно для цикла, покрывающего все вершины.

Граница условия

Условие \( \deg(v) \ge n/2 \) является точным: если допустить степень \( \lfloor n/2 \rfloor \), то существуют негамильтоновы графы. Например, граф, состоящий из двух полных графов \( K_{n/2} \), соединённых одной вершиной (при \( n \) чётном), имеет вершины степени \( n/2 - 1 \) и \( n/2 \), но не является гамильтоновым.

Применение

Теорема Дирака используется в задачах, где требуется гарантированное существование гамильтонова цикла при условии высокой связности графа. Примеры:

• Транспортные сети: проектирование маршрутов, проходящих через все узлы (например, задача коммивояжёра в упрощённой постановке).
• Компьютерные сети: проверка возможности организации циклического обхода всех узлов при условии достаточной степени связности.
• Криптография и теория кодирования: анализ графов, связанных с перестановками и кодами.

Однако на практике условие Дирака часто является слишком сильным, и для реальных графов (например, социальных сетей или графов интернета) оно редко выполняется. Поэтому применяются более слабые условия или эвристические алгоритмы.

Критика и ограничения

Теорема Дирака даёт достаточное, но не необходимое условие. Существует множество гамильтоновых графов, не удовлетворяющих этому условию (например, цикл \( C_n \) при \( n \ge 4 \) имеет степень каждой вершины 2, что меньше \( n/2 \) для \( n > 4 \)). Кроме того, проверка выполнения условия требует вычисления степеней всех вершин, что для больших графов может быть вычислительно затратно, хотя и полиномиально.

Интересные факты

• Теорема Дирака была доказана в 1952 году, а в 1960 году Оре обобщил её, ослабив требование к сумме степеней несмежных вершин.
• Сам Дирак в своей статье также рассмотрел условия для ориентированных графов, но его результат для неориентированных графов стал более известным.
• Теорема является частным случаем теоремы Бонди — Хватала, которая формулируется в терминах замыкания графа: если замыкание графа является полным, то граф гамильтонов.

Источники

• Dirac, G. A. (1952). "Some Theorems on Abstract Graphs". Proceedings of the London Mathematical Society. s3-2 (1): 69–81.
• Оре, О. (1960). "Заметки о гамильтоновых циклах". American Mathematical Monthly. 67 (1): 55.
• Бонди, Дж. А., Хватала, В. (1976). "Метод замыкания для негамильтоновых графов". Journal of Combinatorial Theory, Series B. 20 (3): 251–258.
• Харари, Ф. (1973). Теория графов. Мир, Москва. (Глава 7: Гамильтоновы графы).