Алгоритм нахождения Гамильтонова цикла в условиях теорем Дирака и Оре — различия между версиями
Shersh (обсуждение | вклад) (→Псевдокод) |
Shersh (обсуждение | вклад) м (→Псевдокод) |
||
Строка 15: | Строка 15: | ||
Функция <tex>\mathtt{findHamiltonianCycle}</tex> получает на вход граф <tex> G </tex > и находит гамильтонов цикл в нем. | Функция <tex>\mathtt{findHamiltonianCycle}</tex> получает на вход граф <tex> G </tex > и находит гамильтонов цикл в нем. | ||
− | * <tex> queue </tex> {{---}} очередь вершин графа <tex> G </tex> | + | * <tex> queue </tex> {{---}} очередь вершин графа <tex>G = \left \langle {V, E} \right \rangle</tex> |
− | |||
{| width = 100% | {| width = 100% | ||
|- | |- | ||
| | | | ||
− | '''function''' findHamiltonianCycle( | + | '''function''' findHamiltonianCycle(<tex>\left \langle {V, E} \right \rangle</tex>): |
'''for''' <tex> v \in V</tex>: <font color = "green">// Добавляем все вершины графа в очередь</font> | '''for''' <tex> v \in V</tex>: <font color = "green">// Добавляем все вершины графа в очередь</font> | ||
queue.pushBack(<tex>v</tex>) | queue.pushBack(<tex>v</tex>) |
Версия 21:08, 8 ноября 2015
Содержание
Задача: |
Пусть дан граф теоремы Оре или теоремы Дирака. Требуется найти в нем гамильтонов цикл. | , удовлетворяющий условию
Описание алгоритма
Поступим следующим образом: заведем очередь и положим в нее все вершины нашего графа (не важно в каком порядке). Пусть
. Тогда раз будем делать следующую операцию:- Пусть — это голова очереди, — следующая за ней вершина и так далее. Если между первой и второй вершиной в очереди есть ребро в графе , то перемещаем первую вершину в конец очереди и переходим к следующей итерации.
- Если между первой и второй вершиной в очереди ребра нет, то найдем вершину теорема Оре, либо теорема Дирака, то такая вершина обязательно найдется; чуть позже докажем это явно). После чего поменяем в очереди местами вершины и , и , и , и так далее, пока (то есть пробегает все значения от до значения заданного неравенством). Теперь у нас появилось ребро между первой и второй вершинами в очереди (теперь вторая вершина, это та, которая была до разворота на -й позиции), а также, гарантированно существует ребро между -й и -й вершинами очереди. После этого, так же как и в первом случае, оправляем первую вершину в конец очереди. , где , такую что, ребра (так как у нас для графа выполнена либо
Таким образом после
итераций, мы получаем последовательность (вершины лежащие в очереди), где любые 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(2, i) // Разворачиваем часть перестановки от 2-й до найденной позиции включительно queue.pushBack(queue.top()) queue.pop() |
Доказательство алгоритма
Лемма: |
Каждый раз, когда нам надо искать вершину , где , такую что , такая вершина действительно существует. |
Доказательство: |
Рассмотрим множество теоремы Оре или теоремы Дирака). Из этого следует, что , а это и значит, что искомая вершина существует. | , состоящее из индексов вершин, смежных с , и множество , индексов вершин смежных с . Заметим, что , а , тогда , а значит , в то же время (по условию
Лемма: |
После итераций между каждой парой соседних вершин очереди существует ребро. |
Доказательство: |
Достаточно заметить, что каждую итерацию алгоритма, мы, в случае отсутствия ребра, между | и увеличиваем количество пар соседних в очереди вершин, между которыми есть ребро, как минимум на (это прямое следствие условия поиска нужной вершины, в случае отсутствия ребра), для поиска такой пары требуется не более итераций. Таких пар изначально не более , откуда следует, что после итераций, второе условие будет выполнено.
Теорема: |
Алгоритм находит гамильтонов цикл. |
Доказательство: |
Из предыдущих лемм следует корректность алгоритма. |
Сложность алгоритма
Поиск вершины, удовлетворяющей заданному условию работает за
, а таких поисков будет осуществлено не более чем . Оставшиеся итерации выполняются за . Тогда алгоритм выполняется за .