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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Доказательство алгоритма)
(Псевдокод)
(не показаны 43 промежуточные версии 5 участников)
Строка 1: Строка 1:
 
__TOC__
 
__TOC__
 +
{{Задача
 +
|definition = Пусть дан граф <tex>G = \left \langle {V, E} \right \rangle</tex>, удовлетворяющий условию [[Теорема Оре|теоремы Оре]] или [[Теорема Дирака|теоремы Дирака]]. Требуется найти в нем гамильтонов цикл.
 +
}}
 
== Описание алгоритма ==
 
== Описание алгоритма ==
Алгоритм находит [[Гамильтоновы графы|гамильтонов цикл]] в [[Основные определения теории графов#Неориентированные графы|неориентированном графе]] <tex> \mathbb{G} = (\mathbb{V}, \mathbb{E}) </tex>, если выполняются условия [[Теорема Оре|теоремы Оре]] или выполнена [[теорема Дирака]]. Рассмотрим перестановку вершин <tex> \mathrm{v}_1 \mathrm{v}_2 ... \mathrm{v}_n</tex>, где <tex>n = | \mathbb{V} |</tex>. Если между каждой парой соседних вершин в перестановке существует ребро, то мы получили [[Гамильтоновы графы|Гамильтонов цикл]]. В противном случае, начиная с пары <tex> \mathrm{v}_1 \mathrm{v}_2 </tex>,  начнем последовательно рассматривать пары соседних вершин <tex> \mathrm{v}_i \mathrm{v}_{i+1} </tex>, пока <tex>i \ge n</tex> (Когда <tex>i = n</tex>, за <tex>\mathrm{v}_{i+1}</tex> считаем <tex>\mathrm{v}_{1}</tex>).
 
  
* Если между ними есть ребро, то переходим к следующей паре вершин <tex> \mathrm{v}_{i+1} \mathrm{v}_{i+2}</tex>.  
+
Поступим следующим образом: заведем очередь и положим в нее все вершины нашего графа (не важно в каком порядке). Пусть <tex> n = \left | V \right |</tex>. Тогда <tex>n(n -1)</tex> раз будем делать следующую операцию:
* Если же ребра нет, то найдем такую вершину <tex>\mathrm{v}_j</tex> (то, что она всегда существует, будет показано ниже), что <tex> \mathrm{v}_j \in{\mathbb{V}} \setminus \{ \mathrm{v}_i, \mathrm{v}_{i+1} \} </tex>, и существуют ребра <tex> \mathrm{v}_i \mathrm{v}_j</tex>  и <tex> \mathrm{v}_{i+1} \mathrm{v}_{j+1} </tex> (Если <tex> j = n</tex> , то за <tex>\mathrm{v}_{j+1}</tex> считаем <tex>\mathrm{v}_{1}</tex>).
+
 
** Если <tex>i < j </tex> то перевернем часть перестановки от <tex> i+1 </tex> до <tex> j </tex> (включительно).
+
* Пусть <tex> v_1 </tex> {{---}} это голова очереди, <tex> v_2 </tex> {{---}} следующая за ней вершина и так далее. Если между первой и второй вершиной в очереди есть ребро в графе <tex>G</tex>, то перемещаем первую вершину в конец очереди и переходим к следующей итерации.
** Если <tex> i > j </tex> обменяем в перестановке элементы на позициях <tex> (i + 1 + k)\ \operatorname{mod}\ n </tex> и <tex> (j - k +n)\ \operatorname{mod}\ n </tex>, где <tex>k = \overline{0, (j + n - i)\ \operatorname{div}\ 2}</tex>, то есть считаем <tex>\mathrm{v}_{i}...\mathrm{v}_{j}</tex> равной <tex>\mathrm{v}_{i}...\mathrm{v}_{n}\mathrm{v}_{1}...\mathrm{v}_{j}</tex>. Например, если <tex>n = 10, i = 8, j = 1</tex>, то <tex>\mathrm{v}_9 </tex> и <tex>\mathrm{v}_1</tex> поменяются местами, а <tex>\mathrm{v}_{10}</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 i = 1 to n                          // перебираем все вершины перестановки <tex>P</tex>
+
       '''for''' <tex> v \in V</tex>:                                          <font color = "green">// Добавляем все вершины графа в очередь</font>
     if <tex> v_i v_{i+1} \notin \mathbb{E} </tex>                         // если нет ребра между <tex>v_i v_{i+1} </tex>
+
         queue.pushBack(<tex>v</tex>)
       for <tex>v_j \in \mathbb{V} \setminus \{v_i, v_{i + 1}\}</tex>             // перебираем все остальные вершины  
+
      '''for''' k = 0..n * (n - 1)
         if <tex>v_i v_j \in \mathbb{E}\</tex> && <tex> v_{i+1} v_{j+1} \in \mathbb{E}</tex>     // если есть ребра <tex>v_i v_j,\ v_{i+1} v_{j+1} </tex>
+
        '''if''' (queue.at(0), queue.at(1)) <tex> \notin E</tex>               <font color = "green">// Проверяем существования ребра между первой и второй вершинами очереди</font>
          reverse_subsequence(<tex>P, i+1, j</tex>// разворачиваем часть перестановки <tex>P</tex> от i+1 позиции до j
+
          i = 2                                           
          break                          // переходим к следующей итерации внешнего for                     
+
          '''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>
|width = "310px" |
+
          queue.swapSubQueue(1, i)                        <font color = "green">// Разворачиваем часть перестановки от 1-й до найденной позиции включительно</font>
 +
         queue.pushBack(queue.top())
 +
        queue.pop()
 
|}
 
|}
  
 
== Доказательство алгоритма ==
 
== Доказательство алгоритма ==
Заметим, что поскольку мы сделали нашу перестановку в виде зацикленного списка, то мы можем рассматривать перебор все пар соседних в перестановке вершин, как сдвиг указателя на начало списка. Тогда будем сдвигать указатель на нашу перестановку так, чтобы она начиналась с рассматриваемой пары <tex>\mathrm{v}_i \mathrm{v}_{i+1}</tex>. Если теперь между первыми двумя вершинами есть ребро, то можем переходить к рассмотрению следующей пары, так как в этом случае мы ничего не делаем. Если же ребра нет, то докажем, что обязательно найдется вершина <tex> \mathrm{v}_j \in \mathbb{V} \setminus \{\mathrm{v}_1, \mathrm{v}_{2}\}</tex>, такая что <tex>\mathrm{v}_1 \mathrm{v}_j,\ \mathrm{v}_2 \mathrm{v}_{j+1} \in \mathbb{E} </tex>.
 
  
Пусть <tex>S= \{ i| \mathrm{e}_i = \mathrm{v}_1 \mathrm{v}_i \in \mathbb{E}\}  
+
{{Лемма
\subset  \{3, 4, ...,n\}</tex> и <tex>T = \{ i| f_i=\mathrm{v}_2 \mathrm{v}_{i+1} \in \mathbb{E} \}
+
|statement=Каждый раз, когда нам надо искать вершину <tex>v_i</tex>, где <tex>i > 2</tex>, такую что <tex>v_1v_i, v_2v_{i+1} \in E</tex>, такая вершина действительно существует.
\subset \{2, 3, ...,n-1\}</tex>.
+
|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>, а это и значит, что искомая вершина существует.
Тогда <tex>S \cup T \subset \{2,3,...,n\}</tex>, откуда <tex>|S \cup T |< n</tex>. Но <tex>|S|+|T| = \operatorname{deg}\ v_1 + \operatorname{deg}\ v_2 \ge n</tex> по условию [[Теорема Оре|теоремы Оре]] или [[Теорема Дирака|теоремы Дирака]], в зависимости от наших начальных условий. А значит <tex>S \cap T \ne \varnothing</tex>, следовательно искомая вершина обязательно найдется.
+
}}
Теперь заметим, что после <tex>k</tex>-ой итерации внешнего цикла между всеми парами вершин <tex>\mathrm{v}_{i}, \mathrm{v}_{i+1}</tex>, где <tex>i \le k</tex> существует ребро, а значит после <tex>n</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^2)</tex>. Действительно, количество итераций внешнего цикла <tex>\mathrm{for}</tex> всегда равно <tex>n - 1</tex>, во внутреннем цикле, в худшем случае, будет выполнено <tex>n - 2</tex> итерации, получаем время работы  <tex>O(n^2)</tex>.
+
 
 +
Поиск вершины, удовлетворяющей заданному условию работает за <tex>O(n)</tex>, а таких поисков будет осуществлено не более чем <tex>n</tex>. Оставшиеся <tex>n(n - 2)</tex> итерации выполняются за <tex>O(1)</tex>.
 +
Тогда алгоритм выполняется за <tex>O(n^2)</tex>.
  
 
== См.также ==
 
== См.также ==
Строка 39: Строка 58:
 
*[[Теорема Оре]]
 
*[[Теорема Оре]]
 
*[[теорема Дирака|Теорема Дирака]]
 
*[[теорема Дирака|Теорема Дирака]]
 +
*[[Очередь]]
 +
 +
== Источники информации ==
 +
*[http://rain.ifmo.ru/cat/view.php/theory/graph-circuits-cuts/hamiltonian-2005 Дискретная математика: Алгоритмы {{---}} Гамильтоновы графы]
  
 
[[Категория: Алгоритмы и структуры данных]]
 
[[Категория: Алгоритмы и структуры данных]]
 
[[Категория: Обходы графов]]
 
[[Категория: Обходы графов]]
 +
[[Категория: Гамильтоновы графы]]

Версия 19:49, 31 октября 2016

Задача:
Пусть дан граф [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]\mathtt{findHamiltonianCycle}[/math] получает на вход граф [math] G [/math] и находит гамильтонов цикл в нем.

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

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

Лемма:
Каждый раз, когда нам надо искать вершину [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].

См.также

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