Русская Википедия:Теорема Оре
Теорема Оре — результат в теории графов, доказанный в 1960 году норвежским математиком Ойстином Оре. Теорема даёт достаточное условие для того, чтобы граф был гамильтоновым, по существу утверждая, что граф с «достаточно большим числом рёбер» должен содержать гамильтонов цикл. В частности, теорема рассматривает суммы степеней пар несмежных вершин — если каждая такая пара в сумме даёт как минимум общее число вершин графа, граф является гамильтоновым.
Формальное утверждение
Пусть Шаблон:Math — (конечный и простой) граф с Шаблон:Math вершинами. Обозначим через Шаблон:Math степень вершины Шаблон:Math в Шаблон:Math, то есть число инцидентных вершине Шаблон:Math рёбер. Теорема Оре утверждает, что если
- Шаблон:Math для любой пары несмежных вершин Шаблон:Math и Шаблон:Math графа Шаблон:Math, (*)
то Шаблон:Math является гамильтоновым.
Доказательство
Утверждение эквивалентно тому, что любой негамильтонов граф Шаблон:Mvar нарушает условие (*). Пусть Шаблон:Mvar — негамильтонов граф с Шаблон:Math вершинами. Пусть граф Шаблон:Mvar образован из Шаблон:Mvar путём добавления по одному рёбер, не образующих гамильтонов цикл, пока есть возможность такие рёбра добавлять. Рассмотрим любые две несмежные вершины Шаблон:Math и Шаблон:Math графа Шаблон:Mvar. Добавление ребра Шаблон:Math в Шаблон:Mvar создаёт по меньшей мере один гамильтонов цикл, а рёбра, отличные от Шаблон:Math в этом цикле, должны образовывать гамильтонов путь Шаблон:Math в Шаблон:Mvar с Шаблон:Math и Шаблон:Math. Для каждого индекса Шаблон:Math в диапазоне Шаблон:Math, рассмотрим два возможных ребра в Шаблон:Mvar из Шаблон:Math в Шаблон:Math и из Шаблон:Math в Шаблон:Math. Максимум одно из этих рёбер может присутствовать в Шаблон:Mvar, поскольку в противном случае цикл Шаблон:Math был бы гамильтоновым. Таким образом, общее число рёбер, инцидентных Шаблон:Math или Шаблон:Math, не превосходит числа возможных Шаблон:Math, что равно Шаблон:Math. Поэтому Шаблон:Mvar не удовлетворяет условию (*), которое требует, чтобы общее число рёбер (Шаблон:Math) было больше или равно Шаблон:Math. Поскольку степени вершин Шаблон:Mvar не превосходят степеней в Шаблон:Mvar, то Шаблон:Mvar также не удовлетворяет требованию (*).
Алгоритм
ПалмерШаблон:Sfn описывает следующий простой алгоритм построения гамильтонового цикла в графе, удовлетворяющем условию Оре.
- Выстроим вершины в цикл произвольным образом, игнорируя смежность в графе.
- Если цикл содержит две последовательные несмежные вершины, 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).
Связанные результаты
Теорема Оре является обобщением теоремы Дирака, утверждающей, что если каждая вершина имеет степень не меньшую Шаблон:Math, граф является гамильтоновым. Ясно, что если граф удовлетворяет условию Дирака, сумма степеней пар вершин будет не меньше Шаблон:Math.
В свою очередь, теорема Оре обобщена до теоремы Бонди-Хватала. Можно определить замыкание графа, добавляя для каждой пары несмежных вершин с суммарной степенью как минимум Шаблон:Math ребро, соединяющее эти вершины. Если граф удовлетворяет условию теоремы Оре, его замыкание является полным графом. Теорема Бонди-Хватала утверждает, что граф гамильтонов в том и только в том случае, если его замыкание является гамильтоновым графом. Поскольку полный граф гамильтонов, теорема Оре немедленно вытекает из этой теоремы как следствие.
ВудалШаблон:Sfn нашёл версию теоремы Оре, которая относится к ориентированным графам. Положим, орграф G обладает свойством, что для любых двух вершин u и v либо существует дуга из u в v, либо полустепень исхода u плюс полустепень захода v не меньше числа вершин G. Тогда, согласно теореме Вудала, G содержит ориентированный гамильтонов цикл. Теорему Оре можно получить из теоремы Вудала путём замены каждого ребра парой направленных дуг. Близкая теорема МейнеляШаблон:Sfn утверждает, что сильно связный орграф с n вершинами, обладающий свойством, что для любых несмежных вершин u и v суммарное число рёбер, инцидентных u или v, не меньше 2n − 1, должен быть гамильтоновым.
Теорему Оре можно усилить, дав более строгое требование, чем гамильтоновость, как следствие условия для степеней вершин в теореме. В частности, любой граф, удовлетворяющий условиям теоремы Оре является либо регулярным полным двудольным графом, либо панциклическимШаблон:Sfn.
Примечания
Литература
