Алгоритм нахождения Гамильтонова цикла в условиях теорем Дирака и Оре — различия между версиями
(→Описание алгоритма: тыц) |
м (rollbackEdits.php mass rollback) |
||
(не показано 57 промежуточных версий 7 участников) | |||
Строка 1: | Строка 1: | ||
__TOC__ | __TOC__ | ||
+ | {{Задача | ||
+ | |definition = Пусть дан граф <tex>G = \left \langle {V, E} \right \rangle</tex>, удовлетворяющий условию [[Теорема Оре|теоремы Оре]] или [[Теорема Дирака|теоремы Дирака]]. Требуется найти в нем гамильтонов цикл. | ||
+ | }} | ||
== Описание алгоритма == | == Описание алгоритма == | ||
− | |||
− | * | + | Поступим следующим образом: заведем очередь и положим в нее все вершины нашего графа (не важно в каком порядке). Пусть <tex> n = \left | V \right |</tex>. Тогда <tex>n(n -1)</tex> раз будем делать следующую операцию: |
− | * Если | + | |
− | + | * Пусть <tex> v_1 </tex> {{---}} это голова очереди, <tex> v_2 </tex> {{---}} следующая за ней вершина и так далее. Если между первой и второй вершиной в очереди есть ребро в графе <tex>G</tex>, то перемещаем первую вершину в конец очереди и переходим к следующей итерации. | |
− | + | * Если между первой и второй вершиной в очереди ребра нет, то найдем вершину <tex>v_i</tex>, где <tex>i > 2</tex>, такую что, ребра <tex>v_1v_i, v_2v_{i+1} \in E</tex> (так как у нас для графа выполнена либо [[Теорема Оре|теорема Оре]], либо [[Теорема Дирака|теорема Дирака]], то такая вершина обязательно найдется; чуть позже докажем это явно). После чего поменяем в очереди местами вершины <tex>v_2</tex> и <tex>v_i</tex>, <tex>v_3</tex> и <tex>v_{i-1}</tex>, <tex>v_{2+j} </tex> и <tex>v_{i-j}</tex>, и так далее, пока <tex>2 + j < i - j</tex> (то есть <tex>j</tex> пробегает все значения от <tex>0</tex> до значения заданного неравенством). Теперь у нас появилось ребро между первой и второй вершинами в очереди (теперь вторая вершина, это та, которая была до разворота на <tex>i</tex>-й позиции), а также, гарантированно существует ребро между <tex>i</tex>-й и <tex>(i+1)</tex>-й вершинами очереди. После этого, так же как и в первом случае, оправляем первую вершину в конец очереди. | |
+ | |||
+ | Таким образом после <tex>n</tex> итераций, мы получаем последовательность (вершины лежащие в очереди), где любые 2 соседние вершины соединены ребром, все вершины графа находятся в этой последовательности, и более того, каждая ровно один раз, а также существует ребро между последней и первой вершинами очереди, а это и значит, что мы решили поставленную задачу. | ||
== Псевдокод == | == Псевдокод == | ||
+ | Функция <tex>\mathtt{findHamiltonianCycle}</tex> получает на вход граф <tex> G </tex > и находит гамильтонов цикл в нем. | ||
+ | |||
+ | * <tex> queue </tex> {{---}} очередь вершин графа <tex>G = \left \langle {V, E} \right \rangle</tex> | ||
{| width = 100% | {| width = 100% | ||
|- | |- | ||
| | | | ||
− | + | '''function''' findHamiltonianCycle(<tex>\left \langle {V, E} \right \rangle</tex>): | |
− | + | '''for''' <tex> v \in V</tex>: <font color = "green">// Добавляем все вершины графа в очередь</font> | |
− | + | queue.pushBack(<tex>v</tex>) | |
− | + | '''for''' k = 0..n * (n - 1) | |
− | + | '''if''' (queue.at(0), queue.at(1)) <tex> \notin E</tex> <font color = "green">// Проверяем существования ребра между первой и второй вершинами очереди</font> | |
− | + | i = 2 | |
− | + | '''while''' (queue.at(0), queue.at(i)) <tex> \notin E</tex> '''or''' (queue.at(1), queue.at(i + 1)) <tex> \notin E</tex> | |
− | + | i++ <font color = "green">// Ищем индекс удовлетворяющую условию вершины</font> | |
− | + | queue.swapSubQueue(1, i) <font color = "green">// Разворачиваем часть перестановки от 1-й до найденной позиции включительно</font> | |
+ | queue.pushBack(queue.top()) | ||
+ | queue.pop() | ||
|} | |} | ||
== Доказательство алгоритма == | == Доказательство алгоритма == | ||
− | |||
− | + | {{Лемма | |
− | <tex>\ | + | |statement=Каждый раз, когда нам надо искать вершину <tex>v_i</tex>, где <tex>i > 2</tex>, такую что <tex>v_1v_i, v_2v_{i+1} \in E</tex>, такая вершина действительно существует. |
− | <tex>\subset | + | |proof=Рассмотрим множество <tex>S = \{i\mid v_1v_i \in E\}</tex>, состоящее из индексов вершин, смежных с <tex>v_1</tex>, и множество <tex>T = \{i+1 \mid v_2v_{i+1} \in E\}</tex>, индексов вершин смежных с <tex>v_2</tex>. Заметим, что <tex>S \subset \{3, 4, \ldots, n\}</tex>, а <tex>T \subset \{2, 3, \ldots, n - 1\}</tex>, тогда <tex>S\cup T\subset \{2, 3, \ldots, n\} </tex>, а значит <tex>\left\vert S\cup T\right\vert \leqslant n-1</tex>, в то же время <tex>\left\vert S \right\vert + \left\vert T \right\vert = \operatorname{deg} v_1 + \operatorname{deg} v_2 \geqslant n</tex> (по условию [[Теорема Оре|теоремы Оре]] или [[Теорема Дирака|теоремы Дирака]]). Из этого следует, что <tex>S\cap T\ne \varnothing</tex>, а это и значит, что искомая вершина существует. |
− | + | }} | |
− | + | ||
+ | {{Лемма | ||
+ | |statement=После <tex>n(n - 1)</tex> итераций между каждой парой соседних вершин очереди существует ребро. | ||
+ | |proof=Достаточно заметить, что каждую итерацию алгоритма, мы, в случае отсутствия ребра, между <tex>v_1</tex> и <tex>v_{2}</tex> увеличиваем количество пар соседних в очереди вершин, между которыми есть ребро, как минимум на <tex>1</tex> (это прямое следствие условия поиска нужной вершины, в случае отсутствия ребра), для поиска такой пары требуется не более <tex>n</tex> итераций. Таких пар изначально не более <tex>n</tex>, откуда следует, что после <tex>n</tex> итераций, второе условие будет выполнено. | ||
+ | }} | ||
+ | |||
+ | {{Теорема | ||
+ | |statement=Алгоритм находит гамильтонов цикл. | ||
+ | |proof=Из предыдущих лемм следует корректность алгоритма. | ||
+ | }} | ||
+ | |||
+ | == Сложность алгоритма == | ||
+ | |||
+ | Поиск вершины, удовлетворяющей заданному условию работает за <tex>O(n)</tex>, а таких поисков будет осуществлено не более чем <tex>n</tex>. Оставшиеся <tex>n(n - 2)</tex> итерации выполняются за <tex>O(1)</tex>. | ||
+ | Тогда алгоритм выполняется за <tex>O(n^2)</tex>. | ||
+ | |||
+ | == См.также == | ||
+ | *[[Гамильтоновы графы]] | ||
+ | *[[Теорема Оре]] | ||
+ | *[[теорема Дирака|Теорема Дирака]] | ||
+ | *[[Очередь]] | ||
+ | |||
+ | == Источники информации == | ||
+ | *[http://rain.ifmo.ru/cat/view.php/theory/graph-circuits-cuts/hamiltonian-2005 Дискретная математика: Алгоритмы {{---}} Гамильтоновы графы] | ||
+ | |||
+ | [[Категория: Алгоритмы и структуры данных]] | ||
+ | [[Категория: Обходы графов]] | ||
+ | [[Категория: Гамильтоновы графы]] |
Текущая версия на 19:23, 4 сентября 2022
Содержание
Задача: |
Пусть дан граф теоремы Оре или теоремы Дирака. Требуется найти в нем гамильтонов цикл. | , удовлетворяющий условию
Описание алгоритма
Поступим следующим образом: заведем очередь и положим в нее все вершины нашего графа (не важно в каком порядке). Пусть
. Тогда раз будем делать следующую операцию:- Пусть — это голова очереди, — следующая за ней вершина и так далее. Если между первой и второй вершиной в очереди есть ребро в графе , то перемещаем первую вершину в конец очереди и переходим к следующей итерации.
- Если между первой и второй вершиной в очереди ребра нет, то найдем вершину теорема Оре, либо теорема Дирака, то такая вершина обязательно найдется; чуть позже докажем это явно). После чего поменяем в очереди местами вершины и , и , и , и так далее, пока (то есть пробегает все значения от до значения заданного неравенством). Теперь у нас появилось ребро между первой и второй вершинами в очереди (теперь вторая вершина, это та, которая была до разворота на -й позиции), а также, гарантированно существует ребро между -й и -й вершинами очереди. После этого, так же как и в первом случае, оправляем первую вершину в конец очереди. , где , такую что, ребра (так как у нас для графа выполнена либо
Таким образом после
итераций, мы получаем последовательность (вершины лежащие в очереди), где любые 2 соседние вершины соединены ребром, все вершины графа находятся в этой последовательности, и более того, каждая ровно один раз, а также существует ребро между последней и первой вершинами очереди, а это и значит, что мы решили поставленную задачу.Псевдокод
Функция
получает на вход граф и находит гамильтонов цикл в нем.- — очередь вершин графа
function findHamiltonianCycle(): for : // Добавляем все вершины графа в очередь queue.pushBack( ) for k = 0..n * (n - 1) if (queue.at(0), queue.at(1)) // Проверяем существования ребра между первой и второй вершинами очереди i = 2 while (queue.at(0), queue.at(i)) or (queue.at(1), queue.at(i + 1)) i++ // Ищем индекс удовлетворяющую условию вершины queue.swapSubQueue(1, i) // Разворачиваем часть перестановки от 1-й до найденной позиции включительно queue.pushBack(queue.top()) queue.pop() |
Доказательство алгоритма
Лемма: |
Каждый раз, когда нам надо искать вершину , где , такую что , такая вершина действительно существует. |
Доказательство: |
Рассмотрим множество теоремы Оре или теоремы Дирака). Из этого следует, что , а это и значит, что искомая вершина существует. | , состоящее из индексов вершин, смежных с , и множество , индексов вершин смежных с . Заметим, что , а , тогда , а значит , в то же время (по условию
Лемма: |
После итераций между каждой парой соседних вершин очереди существует ребро. |
Доказательство: |
Достаточно заметить, что каждую итерацию алгоритма, мы, в случае отсутствия ребра, между | и увеличиваем количество пар соседних в очереди вершин, между которыми есть ребро, как минимум на (это прямое следствие условия поиска нужной вершины, в случае отсутствия ребра), для поиска такой пары требуется не более итераций. Таких пар изначально не более , откуда следует, что после итераций, второе условие будет выполнено.
Теорема: |
Алгоритм находит гамильтонов цикл. |
Доказательство: |
Из предыдущих лемм следует корректность алгоритма. |
Сложность алгоритма
Поиск вершины, удовлетворяющей заданному условию работает за
, а таких поисков будет осуществлено не более чем . Оставшиеся итерации выполняются за . Тогда алгоритм выполняется за .