Теорема Оре

Теорема Оре — результат в теорії графів, доведений в 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_i був би гамільтоновим. Таким чином, загальне число ребер, інцидентних 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²).

Література

• 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. — Т. 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.