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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Псевдокод)
(Псевдокод)
Строка 13: Строка 13:
  
 
== Псевдокод ==
 
== Псевдокод ==
Функция <tex>findHamiltonianCycle</tex> получает на вход очередь вершин и находит гамильтонов цикл в графе.
+
Функция <tex>findHamiltonianCycle</tex> получает на вход граф и находит гамильтонов цикл в нем.
  
 
{| width = 100%
 
{| width = 100%
 
|-
 
|-
 
|  
 
|  
   '''function''' <tex>\mathtt{findHamiltonianCycle}(queue):</tex>
+
   '''function''' <tex>\mathtt{findHamiltonianCycle}(G):</tex>
 +
      <tex>\mathtt{Queue}</tex> <tex>\mathtt{queue}</tex>
 +
      '''for''' <tex> v \in V</tex>:                                          <font color = "green">// Добавляем все вершины графа в очередь</font>
 +
        <tex>\mathtt{queue.pushBack}(v)</tex>
 
       '''for''' k = 0...n*(n - 1)
 
       '''for''' k = 0...n*(n - 1)
         '''if''' <tex>(queue.\mathtt{at}(0), queue.\mathtt{at}(1)) \notin E</tex>                  <font color = "green">// Проверяем существования ребра между первой и второй вершинами очереди</font>
+
         '''if''' <tex>(\mathtt{queue.at}(0), \mathtt{queue.at}(1)) \notin E</tex>                  <font color = "green">// Проверяем существования ребра между первой и второй вершинами очереди</font>
           <tex>i = 2</tex>                                             
+
           <tex>\mathtt{i} = 2</tex>                                             
           '''while''' <tex>(queue.\mathtt{at}(0), queue.\mathtt{at}(i)) \notin E</tex> '''or''' <tex>(queue.at(1), queue.at(i + 1)) \notin E</tex>
+
           '''while''' <tex>(\mathtt{queue.at}(0), \mathtt{queue.at}(i)) \notin E</tex> '''or''' <tex>(\mathtt{queue.at}(1), \mathtt{queue.at}(i + 1)) \notin E</tex>
               <tex>i</tex>++                                        <font color = "green">// Ищем индекс удовлетворяющую условию вершины</font>
+
               <tex>\mathtt{i}</tex>++                                        <font color = "green">// Ищем индекс удовлетворяющую условию вершины</font>
           <tex>queue.\mathtt{swapSubQueue}(2, i)</tex>                        <font color = "green">// Разворачиваем часть перестановки от 2-й до найденной позиции включительно</font>
+
           <tex>\mathtt{queue.swapSubQueue}(2, i)</tex>                        <font color = "green">// Разворачиваем часть перестановки от 2-й до найденной позиции включительно</font>
         <tex>queue.\mathtt{pushBack}(queue.\mathtt{top}())</tex>
+
         <tex>\mathtt{queue.pushBack}(\mathtt{queue.top}())</tex>
         <tex>queue.\mathtt{pop}()</tex>
+
         <tex>\mathtt{queue.pop}()</tex>
 
|}
 
|}
  

Версия 20:48, 8 ноября 2015

Задача:
Пусть дан граф [math]G = \left \langle {V, E} \right \rangle[/math], удовлетворяющий условию теоремы Оре или теоремы Дирака. Требуется найти в нем гамильтонов цикл.

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

Поступим следующим образом: заведем очередь и положим в нее все вершины нашего графа (не важно в каком порядке). Пусть [math] n = \left | V \right |[/math]. Тогда [math]n(n -1)[/math] раз будем делать следующую операцию:

  • Пусть [math] v_1 [/math] — это голова очереди, [math] v_2 [/math] — следующая за ней вершина и так далее. Если между первой и второй вершиной в очереди есть ребро в графе [math]G[/math], то перемещаем первую вершину в конец очереди и переходим к следующей итерации.
  • Если между первой и второй вершиной в очереди ребра нет, то найдем вершину [math]v_i[/math], где [math]i \gt 2[/math], такую что, ребра [math]v_1v_i, v_2v_{i+1} \in 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] пробегает все значения от [math]0[/math] до значения заданного неравенством). Теперь у нас появилось ребро между первой и второй вершинами в очереди (теперь вторая вершина, это та, которая была до разворота на [math]i[/math]-й позиции), а также, гарантированно существует ребро между [math]i[/math]-й и [math](i+1)[/math]-й вершинами очереди. После этого, так же как и в первом случае, оправляем первую вершину в конец очереди.

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

Псевдокод

Функция [math]findHamiltonianCycle[/math] получает на вход граф и находит гамильтонов цикл в нем.

 function [math]\mathtt{findHamiltonianCycle}(G):[/math]
     [math]\mathtt{Queue}[/math] [math]\mathtt{queue}[/math]
     for [math] v \in V[/math]:                                          // Добавляем все вершины графа в очередь
       [math]\mathtt{queue.pushBack}(v)[/math]
     for k = 0...n*(n - 1)
       if [math](\mathtt{queue.at}(0), \mathtt{queue.at}(1)) \notin E[/math]                  // Проверяем существования ребра между первой и второй вершинами очереди
         [math]\mathtt{i} = 2[/math]                                             
         while [math](\mathtt{queue.at}(0), \mathtt{queue.at}(i)) \notin E[/math] or [math](\mathtt{queue.at}(1), \mathtt{queue.at}(i + 1)) \notin E[/math]
             [math]\mathtt{i}[/math]++                                         // Ищем индекс удовлетворяющую условию вершины
         [math]\mathtt{queue.swapSubQueue}(2, i)[/math]                        // Разворачиваем часть перестановки от 2-й до найденной позиции включительно
       [math]\mathtt{queue.pushBack}(\mathtt{queue.top}())[/math]
       [math]\mathtt{queue.pop}()[/math]

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

Лемма:
Каждый раз, когда нам надо искать вершину [math]v_i[/math], где [math]i \gt 2[/math], такую что [math]v_1v_i, v_2v_{i+1} \in E[/math], такая вершина действительно существует.
Доказательство:
[math]\triangleright[/math]
Рассмотрим множество [math]S = \{i\mid v_1v_i \in E\}[/math], состоящее из индексов вершин, смежных с [math]v_1[/math], и множество [math]T = \{i+1 \mid v_2v_{i+1} \in E\}[/math], индексов вершин смежных с [math]v_2[/math]. Заметим, что [math]S \subset \{3, 4, \ldots, n\}[/math], а [math]T \subset \{2, 3, \ldots, n - 1\}[/math], тогда [math]S\cup T\subset \{2, 3, \ldots, n\} [/math], а значит [math]\left\vert S\cup T\right\vert \leqslant n-1[/math], в то же время [math]\left\vert S \right\vert + \left\vert T \right\vert = \operatorname{deg} v_1 + \operatorname{deg} v_2 \geqslant n[/math] (по условию теоремы Оре или теоремы Дирака). Из этого следует, что [math]S\cap T\ne \varnothing[/math], а это и значит, что искомая вершина существует.
[math]\triangleleft[/math]
Лемма:
После [math]n(n - 1)[/math] итераций между каждой парой соседних вершин очереди существует ребро.
Доказательство:
[math]\triangleright[/math]
Достаточно заметить, что каждую итерацию алгоритма, мы, в случае отсутствия ребра, между [math]v_1[/math] и [math]v_{2}[/math] увеличиваем количество пар соседних в очереди вершин, между которыми есть ребро, как минимум на [math]1[/math] (это прямое следствие условия поиска нужной вершины, в случае отсутствия ребра), для поиска такой пары требуется не более [math]n[/math] итераций. Таких пар изначально не более [math]n[/math], откуда следует, что после [math]n[/math] итераций, второе условие будет выполнено.
[math]\triangleleft[/math]
Теорема:
Алгоритм находит гамильтонов цикл.
Доказательство:
[math]\triangleright[/math]
Из предыдущих лемм следует корректность алгоритма.
[math]\triangleleft[/math]

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

Поиск вершины, удовлетворяющей заданному условию работает за [math]O(n)[/math], а таких поисков будет осуществлено не более чем [math]n[/math]. Оставшиеся [math]n(n - 2)[/math] итерации выполняются за [math]O(1)[/math]. Тогда алгоритм выполняется за [math]O(n^2)[/math].

См.также

Источники информации