Алгоритм нахождения Гамильтонова цикла в условиях теорем Дирака и Оре — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
м (Псевдокод)
м (Доказательство алгоритма)
Строка 33: Строка 33:
  
 
* Каждый раз, когда нам надо искать вершину <tex>v_i</tex>, где <tex>i > 2</tex>, такую что <tex>v_1v_i, v_2v_{i+1} \in \mathbb{E}</tex>, такая вершина действительно существует.
 
* Каждый раз, когда нам надо искать вершину <tex>v_i</tex>, где <tex>i > 2</tex>, такую что <tex>v_1v_i, v_2v_{i+1} \in \mathbb{E}</tex>, такая вершина действительно существует.
* После <tex>n</tex> итераций между каждой парой соседних вершин очереди существует ребро.
+
* После <tex>n * (n - 1)</tex> итераций между каждой парой соседних вершин очереди существует ребро.
  
 
Докажем первое. Рассмотрим множество <tex>S = \{i\mid v_1v_i \in \mathbb{E}\}</tex>, состоящее из индексов вершин, смежных с <tex>v_1</tex>, и множество <tex>T = \{i+1 \mid v_2v_{i+1} \in \mathbb{E}\}</tex>, индексов вершин смежных с <tex>v_2</tex>. Заметим, что <tex>S \subset \{3, 4,...,n\}</tex>, а <tex>T \subset \{2, 3,...,n - 1\}</tex>, тогда <tex>S\cup T\subset \{2, 3,...,n\} </tex>, а значит <tex>\left\vert S\cup T\right\vert \le n-1</tex>, в то же время <tex>\left\vert S \right\vert + \left\vert T \right\vert = \operatorname{deg} v_1 + \operatorname{deg} v_2 \ge n</tex> (по условию [[Теорема Оре|теоремы Оре]] или [[Теорема Дирака|теоремы Дирака]]). Из этого следует, что <tex>S\cap T\ne \varnothing</tex>, а это и значит, что искомая вершина существует.
 
Докажем первое. Рассмотрим множество <tex>S = \{i\mid v_1v_i \in \mathbb{E}\}</tex>, состоящее из индексов вершин, смежных с <tex>v_1</tex>, и множество <tex>T = \{i+1 \mid v_2v_{i+1} \in \mathbb{E}\}</tex>, индексов вершин смежных с <tex>v_2</tex>. Заметим, что <tex>S \subset \{3, 4,...,n\}</tex>, а <tex>T \subset \{2, 3,...,n - 1\}</tex>, тогда <tex>S\cup T\subset \{2, 3,...,n\} </tex>, а значит <tex>\left\vert S\cup T\right\vert \le n-1</tex>, в то же время <tex>\left\vert S \right\vert + \left\vert T \right\vert = \operatorname{deg} v_1 + \operatorname{deg} v_2 \ge n</tex> (по условию [[Теорема Оре|теоремы Оре]] или [[Теорема Дирака|теоремы Дирака]]). Из этого следует, что <tex>S\cap T\ne \varnothing</tex>, а это и значит, что искомая вершина существует.
  
Для доказательства второй части, достаточно заметить, что каждую итерацию алгоритма, мы, в случае отсутствия ребра, между <tex>v_1</tex> и <tex>v_{2}</tex> увеличиваем количество пар соседних в очереди вершин, между которыми есть ребро, как минимум на 1 (это прямое следствие условия поиска нужной вершины, в случае отсутствия ребра), а таких пар изначально не более <tex>n</tex>. Откуда следует, что после <tex>n</tex> итераций, второе условие будет выполнено.
+
Для доказательства второй части, достаточно заметить, что каждую итерацию алгоритма, мы, в случае отсутствия ребра, между <tex>v_1</tex> и <tex>v_{2}</tex> увеличиваем количество пар соседних в очереди вершин, между которыми есть ребро, как минимум на 1 (это прямое следствие условия поиска нужной вершины, в случае отсутствия ребра), для поиска такой пары требуется не более <tex>n</tex> итераций. Таких пар изначально не более <tex>n</tex>, откуда следует, что после <tex>n</tex> итераций, второе условие будет выполнено.
  
 
== Сложность алгоритма ==
 
== Сложность алгоритма ==

Версия 19:16, 19 декабря 2013

Описание алгоритма

Пусть у нас есть граф [math]\mathbb{G} = \left \langle \mathbb{V, E} \right \rangle[/math], удовлетворяющий условию теоремы Оре или теоремы Дирака, и требуется найти в нем гамильтонов цикл. Поступим следующим образом: заведем очередь и положим в нее все вершины нашего графа(не важно в каком порядке). Теперь [math]n *(n -1)[/math], где [math] n = \left | \mathbb{V}\right |[/math] раз будем делать следующую операцию:

  • Если между первой (здесь и далее первая вершина - вершина в голове очереди) и второй вершиной в очереди есть ребро в графе [math]\mathbb{G}[/math], то перемещаем первую вершину в конец очереди и переходим к следующей итерации.
  • Если между первой и второй вершиной в очереди ребра нет, то найдем вершину [math]v_i[/math], где [math]i \gt 2[/math], такую что, ребра [math]v_1v_i, v_2v_{i+1} \in \mathbb{E}[/math] (так как у нас для графа выполнена либо теорема Оре, либо теорема Дирака, то такая вершина обязательно найдется; чуть позже мы это докажем явно). После чего поменяем в очереди местами вершины [math]v_2[/math] и [math]v_i[/math], [math]v_3[/math] и [math]v_{i-1}[/math], [math]v_{2+j} [/math] и [math]v_{i-j}[/math], и так далее, пока [math]2 + j \lt i - j[/math] (то есть [math]j[/math] пробегает все значения от 0 до значения заданного неравенством). Теперь у нас появилось ребро между первой и второй вершинами в очереди (теперь вторая вершина, это та, которая была до разворота на [math]i[/math]-й позиции), а также, гарантированно существует ребро между [math]i[/math]-й и [math](i+1)[/math]-й вершинами очереди. После этого, так же как и в первом случае, оправляем первую вершину в конец очереди.

Таким образом после [math]n[/math] итераций, мы получаем последовательность (вершины лежащие в очереди), где любые 2 соседние вершины соединены ребром, все вершины графа находятся в этой последовательности, и более того, каждая ровно один раз, а также существует ребро между последней и первой вершинами очереди, а это и значит, что мы решили поставленную задачу.

Псевдокод

 g[][] - булевская матрица смежности
 Queue queue                                           // создаем очередь
 for i = 0 to n - 1                                     
   queue.pushBack(v[i])                                // добавляем в очередь все вершины графа
 for k = 0 to n*(n - 1)                                    // пока не проделано нужное количество итераций
   if not g[queue.at(0), queue.at(1)]                  // проверяем существования ребра между первой и второй вершинами очереди
     i = 2                                             
     while not g[queue.at(0), queue.at(i)] 
       or not g[queue.at(1), queue.at(i + 1)]          // ищем индекс удовлетворяющую условию вершины
         i++                                             
     queue.swapSubQueue(2, i)                          // разворачиваем часть перестановки от 2-й до найденной позиции включительно
   queue.pushBack(queue.top())                         // Добавляем первую вершину в конец очереди
   queue.pop()                                         // а из начала очереди удаляем
 

Доказательство алгоритма

Для доказательства корректности алгоритма достаточно показать:

  • Каждый раз, когда нам надо искать вершину [math]v_i[/math], где [math]i \gt 2[/math], такую что [math]v_1v_i, v_2v_{i+1} \in \mathbb{E}[/math], такая вершина действительно существует.
  • После [math]n * (n - 1)[/math] итераций между каждой парой соседних вершин очереди существует ребро.

Докажем первое. Рассмотрим множество [math]S = \{i\mid v_1v_i \in \mathbb{E}\}[/math], состоящее из индексов вершин, смежных с [math]v_1[/math], и множество [math]T = \{i+1 \mid v_2v_{i+1} \in \mathbb{E}\}[/math], индексов вершин смежных с [math]v_2[/math]. Заметим, что [math]S \subset \{3, 4,...,n\}[/math], а [math]T \subset \{2, 3,...,n - 1\}[/math], тогда [math]S\cup T\subset \{2, 3,...,n\} [/math], а значит [math]\left\vert S\cup T\right\vert \le n-1[/math], в то же время [math]\left\vert S \right\vert + \left\vert T \right\vert = \operatorname{deg} v_1 + \operatorname{deg} v_2 \ge n[/math] (по условию теоремы Оре или теоремы Дирака). Из этого следует, что [math]S\cap T\ne \varnothing[/math], а это и значит, что искомая вершина существует.

Для доказательства второй части, достаточно заметить, что каждую итерацию алгоритма, мы, в случае отсутствия ребра, между [math]v_1[/math] и [math]v_{2}[/math] увеличиваем количество пар соседних в очереди вершин, между которыми есть ребро, как минимум на 1 (это прямое следствие условия поиска нужной вершины, в случае отсутствия ребра), для поиска такой пары требуется не более [math]n[/math] итераций. Таких пар изначально не более [math]n[/math], откуда следует, что после [math]n[/math] итераций, второе условие будет выполнено.

Сложность алгоритма

Алгоритм работает за [math]O(n^2)[/math]. Действительно, количество итераций внешнего цикла [math]\mathrm{for}[/math] всегда равно [math]n[/math]. Поиск вершины, удовлетворяющей заданному условию тоже работает за [math]O(n)[/math], итого время работы [math]O(n^2)[/math].

См.также