Теорема Оре

Материал из Википедии — свободной энциклопедии
Перейти к навигации Перейти к поиску

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

Формальное утверждение[править | править код]

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

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

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

Доказательство[править | править код]

Утверждение эквивалентно тому, что любой негамильтонов граф G нарушает условие (*). Пусть G — негамильтонов граф с n ≥ 3 вершинами. Пусть граф H образован из G путём добавления по одному рёбер, не образующих гамильтонов цикл, пока есть возможность такие рёбра добавлять. Рассмотрим любые две несмежные вершины x и y графа H. Добавление ребра xy в H создаёт по меньшей мере один гамильтонов цикл, а рёбра, отличные от xy в этом цикле, должны образовывать гамильтонов путь v1v2...vn в H с x = v1 и y = vn. Для каждого индекса i в диапазоне 2 ≤ in, рассмотрим два возможных ребра в H из v1 в vi и из vi − 1 в vn. Максимум одно из этих рёбер может присутствовать в H, поскольку в противном случае цикл v1v2...vi − 1vnvn − 1...vi был бы гамильтоновым. Таким образом, общее число рёбер, инцидентных v1 или vn, не превосходит числа возможных i, что равно n − 1. Поэтому H не удовлетворяет условию (*), которое требует, чтобы общее число рёбер (deg v1 + deg vn) было больше или равно n. Поскольку степени вершин G не превосходят степеней в H, то G также не удовлетворяет требованию (*).

Алгоритм[править | править код]

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

  1. Выстроим вершины в цикл произвольным образом, игнорируя смежность в графе.
  2. Если цикл содержит две последовательные несмежные вершины, 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).

Связанные результаты[править | править код]

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

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

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

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

Примечания[править | править код]

Литература[править | править код]