Теорема Ора
Теорема Оре — результат теории графов, доказанный в 1960 году норвежским математиком Ойстейном Оре . Он дает достаточное условие для того, чтобы граф был гамильтоновым , по существу утверждая, что граф с достаточным количеством ребер должен содержать цикл Гамильтона . В частности, теорема рассматривает сумму степеней пар несмежных вершин : если каждая такая пара имеет сумму, по крайней мере равную общему количеству вершин в графе, то граф является гамильтоновым.
Официальное заявление
[ редактировать ]Пусть G — (конечный и простой) граф с n ≥ 3 вершинами. Обозначим через deg v степень вершины v в G т.е. количество ребер инцидентных вершине в G. v , , Тогда теорема Оре утверждает, что если
| deg v + deg w ≥ n для каждой пары различных несмежных вершин v и w графа G | (∗) |
тогда G гамильтонова .
Доказательство
[ редактировать ]
Это эквивалентно показать, что каждый негамильтонов граф G не подчиняется условию (∗) . Соответственно, пусть G — граф с n ≥ 3 вершинами, который не является гамильтоновым, и пусть H образован из G путем добавления ребер по одному, которые не создают гамильтонов цикл, до тех пор, пока не перестанут добавляться ребра. Пусть x и y — любые две несмежные вершины в H . Тогда добавление ребра xy в H создаст по крайней мере один новый гамильтонов цикл, а ребра, отличные от xy, в таком цикле должны образовать гамильтонов путь v 1 v 2 ... v n в H с x = v 1 и y = v. н . Для каждого индекса i в диапазоне 2 ≤ i ≤ n рассмотрим два возможных ребра в H от v 1 до v i и от v i − 1 до v n . может присутствовать не более одного из этих двух ребер В H , иначе цикл v 1 v 2 ... v i - 1 v n v n - 1 ... v i был бы гамильтоновым циклом. Таким образом, общее количество ребер, инцидентных либо v 1 , либо v n, не более чем равно числу вариантов выбора i , которое равно n − 1 . Следовательно, H не подчиняется свойству (∗) , которое требует, чтобы это общее количество ребер ( deg v 1 + deg v n ) быть больше или равно n . Поскольку степени вершин в G не более чем равны степеням в H , отсюда следует, что G также не подчиняется свойству (∗) .
Алгоритм
[ редактировать ]Палмер (1997) описывает следующий простой алгоритм построения гамильтонова цикла в графе, удовлетворяющем условию Ора.
- Расположите вершины произвольно в цикле, игнорируя смежности в графе.
- Пока цикл содержит две последовательные вершины vi , и vi которые не являются соседними в +1 графе, выполните следующие два шага:
- Найдите индекс j такой, что все четыре вершины v i , vi различны и такой , + 1 , v j и v j + 1 что граф содержит ребра от v i до v j и от v j + 1 до v. я + 1
- Поменяйте местами часть цикла между vi ( + 1 и v j включительно).
Каждый шаг увеличивает количество последовательных пар в цикле, которые являются соседними в графе, на одну или две пары (в зависимости от того, являются ли уже соседними v j и v j + 1 ), поэтому внешний цикл может произойти не более n раз. до завершения алгоритма, где n — количество вершин в данном графе. аналогичному приведенному в доказательстве теоремы, искомый индекс j должен существовать, иначе несмежные вершины vi 1 и vi + По рассуждению , имели бы слишком малую суммарную степень. Поиск i и j и обращение части цикла можно выполнить за время O( n ). Следовательно, общее время работы алгоритма составит O( n 2 ), соответствующее количеству ребер во входном графе.
Связанные результаты
[ редактировать ]Теорема Ора является обобщением теоремы Дирака о том, что, когда каждая вершина имеет степень не ниже n /2 , граф является гамильтоновым. Ибо если граф удовлетворяет условию Дирака, то очевидно, что каждая пара вершин имеет степени, добавляющие по крайней мере n .
В свою очередь, теорема Ора обобщается теоремой Бонди–Хваталя . Можно определить операцию замыкания в графе, в которой всякий раз, когда две несмежные вершины имеют суммы степеней не менее n , добавляется ребро, соединяющее их; если граф удовлетворяет условиям теоремы Оре, его замыкание является полным графом . Теорема Бонди – Шваталя утверждает, что граф гамильтонов тогда и только тогда, когда его замыкание гамильтоново; поскольку полный граф является гамильтоновым, теорема Ора является непосредственным следствием.
Вудалл (1972) нашел версию теоремы Ора, применимую к ориентированным графам . Предположим, что орграф G обладает свойством, заключающимся в том, что для каждых двух вершин u и v либо существует ребро, ведущее от u к v , либо исходящая степень u плюс входная степень v равна или превышает количество вершин в G . Тогда согласно теореме Вудала G содержит направленный гамильтонов цикл. Теорему Ора можно получить из Вудала, заменив каждое ребро в данном неориентированном графе парой ориентированных ребер. Тесно связанная с ней теорема Мейниэля (1973) утверждает, что орграф с n -вершинами сильно связный , свойство которого состоит в том, что для каждых двух несмежных вершин u и v общее количество ребер, инцидентных u или v, составляет не менее 2 n - 1, должно быть быть гамильтоновым.
Теорему Ора также можно усилить, чтобы дать более сильный вывод, чем гамильтоновость, как следствие условия степени в теореме. В частности, каждый граф, удовлетворяющий условиям теоремы Оре, является либо регулярным полным двудольным графом , либо панциклическим ( Бонди, 1971 ).
Ссылки
[ редактировать ]- Бонди, Дж. А. (1971), «Панциклические графы I», Журнал комбинаторной теории, серия B , 11 (1): 80–84, doi : 10.1016/0095-8956(71)90016-5 .
- Мейниэль, М. (1973), «Достаточное условие существования гамильтоновой схемы в ориентированном графе», Журнал комбинаторной теории, серия B (на французском языке), 14 (2): 137–147, doi : 10.1016 / 0095-8956(73)90057-9 .
- Оре, Ø. (1960), «Заметки о схемах Гамильтона», American Mathematical Monthly , 67 (1): 55, doi : 10.2307/2308928 , JSTOR 2308928 .
- Палмер, Э.М. (1997), «Скрытый алгоритм теоремы Ора о гамильтоновых циклах», Computers & Mathematics with Applications , 34 (11): 113–119, doi : 10.1016/S0898-1221(97)00225-3 , MR 1486890 .
- Вудалл, Д.Р. (1972), «Достаточные условия для схем в графах», Труды Лондонского математического общества , третья серия, 24 : 739–755, doi : 10.1112/plms/s3-24.4.739 , MR 0318000 .