Теорема Оре (Mykjybg Kjy)

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

Формальное утверждение

Пусть G — (конечный и простой) граф с n ≥ 3 вершинами. Обозначим через deg v степень вершины v в G, то есть число инцидентных вершине v рёбер. Теорема Оре утверждает, что если

deg v + deg w ≥ n для любой пары несмежных вершин v и w графа G, (*)

то G является гамильтоновым.

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

Утверждение эквивалентно тому, что любой негамильтонов граф G нарушает условие (*). Пусть G — негамильтонов граф с n ≥ 3 вершинами. Пусть граф H образован из G путём добавления по одному рёбер, не образующих гамильтонов цикл, пока есть возможность такие рёбра добавлять. Рассмотрим любые две несмежные вершины x и y графа H. Добавление ребра xy в H создаёт по меньшей мере один гамильтонов цикл, а рёбра, отличные от xy в этом цикле, должны образовывать гамильтонов путь v₁v₂...v_n в H с x = v₁ и y = v_n. Для каждого индекса i в диапазоне 2 ≤ i ≤ n, рассмотрим два возможных ребра в H из v₁ в v_i и из v_{i − 1} в v_n. Максимум одно из этих рёбер может присутствовать в H, поскольку в противном случае цикл v₁v₂...v_{i − 1}v_nv_{n − 1}...v_iv₁ был бы гамильтоновым. Таким образом, общее число рёбер, инцидентных v₁ или v_n, не превосходит числа возможных i, что равно n − 1. Поэтому H не удовлетворяет условию (*), которое требует, чтобы общее число рёбер (deg v₁ + deg v_n) было больше или равно n. Поскольку степени вершин G не превосходят степеней в H, то G также не удовлетворяет требованию (*).

Алгоритм

Палмер описывает следующий простой алгоритм построения гамильтонового цикла в графе, удовлетворяющем условию Оре.

1. Выстроим вершины в цикл произвольным образом, игнорируя смежность в графе.
2. Если цикл содержит две последовательные несмежные вершины, v_i и v_i + 1, осуществим следующие шаги:
   • Находим индекс j, для которого четыре вершины v_i, v_i + 1, v_j и v_j + 1 все различны и граф содержит рёбра из v_i в v_j и из v_j + 1 в v_i + 1
   • Часть цикла между v_i + 1 и v_j (включительно) выстраиваем в обратном порядке.

Каждый шаг увеличивает число последовательных смежных пар на одну или две пары (зависит от того, являются ли v_j и v_j + 1 уже смежными), так что внешний цикл алгоритма может отработать максимум n раз, прежде чем он прервётся, где n — число вершин данного графа. По причинам, аналогичным приведённым в доказательстве теоремы, индекс j должен существовать, в противном случае несмежные вершины v_i и v_i + 1 имеют слишком маленькую суммарную степень. Поиск i и j с последующим инвертированием части цикла можно осуществить за время O(n). Таким образом, общее время работы алгоритма равно O(n²).

Связанные результаты

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

В свою очередь, теорема Оре обобщена до теоремы Бонди-Хватала. Можно определить замыкание графа, добавляя для каждой пары несмежных вершин с суммарной степенью как минимум n ребро, соединяющее эти вершины. Если граф удовлетворяет условию теоремы Оре, его замыкание является полным графом. Теорема Бонди-Хватала утверждает, что граф гамильтонов в том и только в том случае, если его замыкание является гамильтоновым графом. Поскольку полный граф гамильтонов, теорема Оре немедленно вытекает из этой теоремы как следствие.

Вудал нашёл версию теоремы Оре, которая относится к ориентированным графам. Положим, орграф G обладает свойством, что для любых двух вершин u и v либо существует дуга из u в v, либо полустепень исхода u плюс полустепень захода v не меньше числа вершин G. Тогда, согласно теореме Вудала, G содержит ориентированный гамильтонов цикл. Теорему Оре можно получить из теоремы Вудала путём замены каждого ребра парой направленных дуг. Близкая теорема Мейнеля утверждает, что сильно связный орграф с n вершинами, обладающий свойством, что для любых несмежных вершин u и v суммарное число рёбер, инцидентных u или v, не меньше 2n − 1, должен быть гамильтоновым.

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

Литература

• J. A. Bondy. Pancyclic graphs I // Journal of Combinatorial Theory, Series B. — 1971. — Т. 11, вып. 1. — С. 80—84. — doi:10.1016/0095-8956(71)90016-5.
• M. Meyniel. Une condition suffisante d'existence d'un circuit hamiltonien dans un graphe orienté // Journal of Combinatorial Theory. — 1973. — Т. 14, вып. 2. — С. 137—147. — doi:10.1016/0095-8956(73)90057-9.
• Ø. Ore. Note on Hamilton circuits // American Mathematical Monthly. — 1960. — Т. 67, вып. 1. — .
• E. M. Palmer. The hidden algorithm of Ore's theorem on Hamiltonian cycles // Computers & Mathematics with Applications. — 1997. — Т. 34, вып. 11. — С. 113–119. — doi:10.1016/S0898-1221(97)00225-3.
• D. R. Woodall. Sufficient conditions for circuits in graphs // Proceedings of the London Mathematical Society. — 1972. — Т. 24. — С. 739–755.