Теорема Оре — результат в теорії графів, доведений в 1960 році норвезьким математиком Ойстином Оре. Теорема дає достатню умову для того, щоб граф був гамільтоновим, по суті стверджуючи, що граф з «досить великим числом ребер» повинен містити гамільтонів цикл. Зокрема, теорема розглядає суми степенів пар несуміжних вершин - якщо кожна така пара в сумі дає як мінімум загальне число вершин графу, граф є гамільтоновим.
Формальне затвердження Нехай — (скінченний і простий) граф з вершинами. Позначимо через степінь вершини в , тобто число інцидентних вершині ребер. Теорема Оре стверджує, якщо для будь-якої пари несуміжних вершин і графу , (*) то є гамільтоновим.
Доведення Твердження еквівалентно тому, що будь-який негамільтоновий граф порушує умову (*). Нехай — негамільтонів граф з вершинами. Нехай граф утворений з шляхом добавлення по одному ребру, не утворюючи гамільтонів цикл, поки є можливість додавати такі ребра. Розглянемо будь-які дві несуміжні вершини і графу . Додавання ребра в створює щонайменше один гамільтонів цикл, а ребра, відмінні від в цьому циклі, повинні утворювати гамільтонів шлях в з і . Для кожного індексу в діапазоні , розглянемо два можливих ребра в з в і з в . Максимум одне з цих ребер може бути присутнім в , оскільки в іншому випадку цикл був би гамільтоновим. Таким чином, загальне число ребер, інцидентних або , не перевищує числа можливих , що дорівнює . Тому не задовольняє умову (*), яке вимагає, щоб загальне число ребер () було більше або дорівнювало . Оскільки степень вершин не є вищим за степінь в , то також не задовольняє умову (*).
Алгоритм Палмер описує наступний простий алгоритм побудови гамільтонового циклу в графі, що задовольняє умові Оре.
Вибудуємо вершини в цикл довільним чином, ігноруючи суміжності в графі. Якщо цикл містить дві послідовні несуміжні вершини, vi і vi + 1, здійснимо наступні кроки: Знаходимо індекс j, для якого чотири вершини vi, vi + 1, vj і vj + 1 різні і граф містить ребра з vi в vj і з vj + 1 в vi + 1 Частину циклу між vi + 1 і vj (включно) вибудовуємо в зворотному порядку.
Кожен крок збільшує число послідовних суміжних пар на одну або дві пари (залежить від того, чи є vj і vj + 1 вже суміжними), так що зовнішній цикл алгоритму може відпрацювати максимум n раз, перш ніж він перерветься, де n — число вершин даного графу. З причин, аналогічних, що є в доведенні теореми, індекс j повинен існувати, в іншому випадку несуміжні вершини vi і vi + 1 мають занадто малий сумарний степінь. Пошук i і j можна здійснити за час O(n). Таким чином, загальний час роботи алгоритму O(n2).
Примітки
Література