Теорема Оре

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

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

Пусть \( G \) — конечный простой граф (неориентированный, без петель и кратных рёбер) с числом вершин \( n \ge 3 \). Если для любой пары несмежных вершин \( u \) и \( v \) выполняется условие:

\[ \deg(u) + \deg(v) \ge n, \]

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

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

История

Теорема была опубликована Эйстейном Оре в 1960 году в статье «Note on Hamilton circuits» в журнале American Mathematical Monthly. Оре (1899–1968) — норвежский математик, известный работами в области теории графов, теории колец и алгебраической геометрии. Его результат стал важным шагом в развитии достаточных условий гамильтоновости, стимулировав дальнейшие исследования в этой области.

Доказательство

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

Основные шаги доказательства:

1. Пусть \( G \) удовлетворяет условию теоремы, но не является гамильтоновым. Добавим к \( G \) рёбра до тех пор, пока не получим максимальный негамильтонов граф \( H \) (добавление любого нового ребра делает граф гамильтоновым).
2. В \( H \) существуют две несмежные вершины \( u \) и \( v \), соединение которых ребром создаёт гамильтонов цикл. Этот цикл, после удаления ребра \( uv \), даёт гамильтонов путь \( P \) от \( u \) до \( v \).
3. Используя условие \( \deg_H(u) + \deg_H(v) \ge n \), можно показать, что существует вершина \( w \) на пути \( P \), такая что \( u \) смежна с \( w \), а \( v \) смежна со следующей за \( w \) вершиной. Это позволяет построить цикл, не использующий ребро \( uv \), что противоречит максимальности \( H \).

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

Теорема Дирака (1952)

Теорема Дирака является частным случаем теоремы Оре: если степень каждой вершины не меньше \( n/2 \), то для любой пары несмежных вершин сумма степеней не меньше \( n \), и граф гамильтонов. Теорема Оре ослабляет это условие, требуя его только для несмежных вершин.

Теорема Бонди — Хватала (1976)

Теорема Бонди — Хватала обобщает теорему Оре, вводя понятие замыкания графа. Замыкание \( \operatorname{cl}(G) \) графа \( G \) получается последовательным добавлением рёбер между несмежными вершинами, сумма степеней которых не меньше \( n \). Теорема утверждает, что \( G \) гамильтонов тогда и только тогда, когда гамильтоново его замыкание. Если замыкание является полным графом, то \( G \) гамильтонов — это эквивалентно условию теоремы Оре.

Теорема Поша (1962)

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

Примеры применения

Пример 1: Граф, удовлетворяющий условию

Рассмотрим граф с 5 вершинами, имеющий следующую структуру: вершины \( A, B, C, D, E \). Степени вершин: \( \deg(A)=3, \deg(B)=3, \deg(C)=2, \deg(D)=2, \deg(E)=2 \). Сумма степеней для несмежных пар: \( A \) и \( C \) (3+2=5 ≥ 5), \( A \) и \( D \) (3+2=5), \( A \) и \( E \) (3+2=5), \( B \) и \( C \) (3+2=5), \( B \) и \( D \) (3+2=5), \( B \) и \( E \) (3+2=5). Условие выполнено, граф гамильтонов.

Пример 2: Граф, не удовлетворяющий условию

Граф «два треугольника, соединённые вершиной»: вершины \( A, B, C, D, E \) (n=5). Степени: \( \deg(A)=4, \deg(B)=2, \deg(C)=2, \deg(D)=2, \deg(E)=2 \). Несмежные вершины: \( B \) и \( C \) (2+2=4 < 5), \( B \) и \( D \) (4<5), \( C \) и \( D \) (4<5). Условие не выполнено, хотя граф является гамильтоновым (цикл A-B-C-A-D-E-A). Этот пример иллюстрирует, что условие не является необходимым.

Ограничения и обобщения

Теорема Оре применима только к простым графам с числом вершин не менее трёх. Она не работает для ориентированных графов, мультиграфов или графов с петлями. Для орграфов существуют аналогичные условия, например, теорема Гуйя — Ури.

Обобщения теоремы Оре включают:

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

Применение в задачах

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

Источники

• Ore, O. (1960). «Note on Hamilton circuits». American Mathematical Monthly, 67(1), 55.
• Дистель, Р. (2002). Теория графов. Новосибирск: Издательство Института математики.
• Харари, Ф. (1973). Теория графов. Москва: Мир.
• Bondy, J. A., & Murty, U. S. R. (2008). Graph Theory. Springer.