Теорема руды - Ores theorem - Wikipedia

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

Теорема руда это результат теория графов доказано в 1960 г. норвежский язык математик Øystein Ore. Он дает достаточное условие для того, чтобы граф был Гамильтониан, по сути утверждая, что граф с достаточно большим количеством ребер должен содержать Цикл Гамильтона. В частности, теорема рассматривает сумму градусы пар несмежный вершины: если каждая такая пара имеет сумму, которая по крайней мере равна общему количеству вершин в графе, то граф является гамильтоновым.

Официальное заявление

Позволять $грамм$ быть (конечным и простым) график с $п \geq 3$ вершины. Обозначим через $град v$ степень вершины $v$ в $грамм$ , т.е. количество инцидент края в $грамм$ к $v$ . Тогда теорема Оре утверждает, что если

град v + град ш \geq п

для каждой пары различных несмежный вершины

v

и

ш

из

грамм

(∗)

тогда $грамм$ является Гамильтониан.

Доказательство

Иллюстрация к доказательству теоремы Оре. В графе с гамильтоновым путем

v 1 ... v п

но не гамильтонов цикл, самое большее одно из двух ребер

v 1 v я

и

v я - 1 v п

(показаны синими пунктирными кривыми) могут существовать. Ибо, если они оба существуют, то добавляем их к пути и удаляем (красный) край

v я - 1 v я

произвел бы гамильтонов цикл.

Это эквивалентно показать, что любой негамильтонов граф $грамм$ не подчиняется условию (∗). Соответственно пусть $грамм$ быть графиком на $п \geq 3$ вершин, не являющихся гамильтоновыми, и пусть $ЧАС$ быть сформированным из $грамм$ добавляя ребра по одному, которые не создают гамильтонов цикл, пока больше не будет добавлено ребер. Позволять $Икс$ и $у$ - любые две несмежные вершины из $ЧАС$ . Затем добавляем край $ху$ к $ЧАС$ создаст по крайней мере один новый гамильтонов цикл, а ребра, отличные от $ху$ в таком цикле должен образоваться Гамильтонов путь $v 1 v 2 ... v п$ в $ЧАС$ с $Икс = v 1$ и $у = v п$ . Для каждого индекса $я$ В диапазоне $2 \leq я \leq п$ рассмотрим два возможных ребра в $ЧАС$ из $v 1$ к $v я$ и из $v я - 1$ к $v п$ . Максимум одно из этих двух ребер может присутствовать в $ЧАС$ , иначе цикл $v 1 v 2 ... v я - 1 v п v п - 1 ... v я$ был бы гамильтоновым циклом. Таким образом, общее количество ребер, инцидентных либо $v 1$ или же $v п$ не больше, чем количество вариантов выбора $я$ , который $п - 1$ . Следовательно, $ЧАС$ не подчиняется собственности (∗), что требует, чтобы это общее количество ребер ( $град v 1 + град v п$ ) быть больше или равно $п$ . Поскольку степени вершин в $грамм$ не более чем равны степеням в $ЧАС$ , следует, что $грамм$ также не подчиняется собственности(∗).

Алгоритм

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

Организуйте вершины произвольно в цикл, игнорируя примыкания в графе.
Пока цикл содержит две последовательные вершины v_я и v_я + 1 несмежные на графике, выполните следующие два шага:
- Искать индекс j такие, что четыре вершины v_я, v_я + 1, v_j, и v_j + 1 все различны и такие, что граф содержит ребра из v_я к v_j и из v_j + 1 к v_я + 1
- Измените часть цикла между v_я + 1 и v_j (включительно).

Каждый шаг увеличивает количество следующих друг за другом пар в цикле, которые являются смежными в графе, на одну или две пары (в зависимости от того, v_j и v_j + 1 уже смежны), поэтому внешний цикл может происходить не более чем п раз до завершения алгоритма, где п - количество вершин в данном графе. Рассуждениями, аналогичными приведенным в доказательстве теоремы, искомый индекс j должны существовать, иначе несмежные вершины v_я и v_я + 1 была бы слишком мала общая степень. обнаружение я и j, и обратная часть цикла, могут быть выполнены за время O (п). Следовательно, общее время работы алгоритма O (п²), соответствующее количеству ребер во входном графе.

Связанные результаты

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

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

Вудолл (1972) нашел версию теоремы Оре, которая применима к ориентированные графы. Предположим орграф грамм обладает тем свойством, что для каждых двух вершин ты и v, либо есть край от ты к v или превышение ты плюс степень v равно или превышает количество вершин в грамм. Тогда, согласно теореме Вудалла, грамм содержит ориентированный гамильтонов цикл. Теорема Оре может быть получена из Вудалла заменой каждого ребра в данном неориентированном графе парой ориентированных ребер. Тесно связанная теорема Мейниэль (1973) заявляет, что п-вертекс сильно связанный орграф со свойством, что для каждых двух несмежных вершин ты и v, общее количество ребер, инцидентных ты или же v не менее 2п - 1 должен быть гамильтоновым.

Теорема Оре также может быть усилена, чтобы дать более сильный вывод, чем гамильтоничность, как следствие условия степени в теореме. В частности, каждый граф, удовлетворяющий условиям теоремы Оре, является либо обычный полный двудольный граф или это панциклический (Бонди 1971 ).

Теорема руды - Ores theorem - Wikipedia

Содержание

Официальное заявление

Доказательство

Алгоритм

Связанные результаты

Рекомендации