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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Доказательство алгоритма)
(Доказательство алгоритма)
Строка 30: Строка 30:
 
Покажем, что такая вершина обязательно найдется.
 
Покажем, что такая вершина обязательно найдется.
 
Пусть <tex>S= \{ i| \mathrm{e}_i = \mathrm{v}_k \mathrm{v}_i \in \mathbb{E}\}  
 
Пусть <tex>S= \{ i| \mathrm{e}_i = \mathrm{v}_k \mathrm{v}_i \in \mathbb{E}\}  
\subset  \{1, 2, ...,n\} \setminus \{\mathrm{k},\mathrm{k+1}\}
+
\subset  \{1, 2, ...,n\} \setminus \{k,k+1\} </tex>  
</tex> и <tex>T = \{ i| f_i=\mathrm{v}_2 \mathrm{v}_{i+1} \in \mathbb{E} \}
+
и <tex>T = \{ i| f_i=\mathrm{v}_k \mathrm{v}_{i+1} \in \mathbb{E} \}
\subset  \{2, 3, ...,n-1\}</tex>.
+
\subset  \{1, 2, ...,n-1\} \setminus \{k\} </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>S \cup T \subset \{1,2,...,n\} \setminus \{k\} </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> итераций мы найдем цикл.
 
Теперь заметим, что после <tex>k</tex>-ой итерации внешнего цикла между всеми парами вершин <tex>\mathrm{v}_{i}, \mathrm{v}_{i+1}</tex>, где <tex>i \le k</tex> существует ребро, а значит после <tex>n</tex> итераций мы найдем цикл.
  

Версия 20:19, 6 ноября 2013

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

Алгоритм находит гамильтонов цикл в неориентированном графе [math] \mathbb{G} = (\mathbb{V}, \mathbb{E}) [/math], если выполняются условия теоремы Оре или выполнена теорема Дирака. Рассмотрим перестановку вершин [math] \mathrm{v}_1 \mathrm{v}_2 ... \mathrm{v}_n[/math], где [math]n = | \mathbb{V} |[/math]. Если между каждой парой соседних вершин в перестановке существует ребро, то мы получили Гамильтонов цикл. В противном случае, начиная с пары [math] \mathrm{v}_1 \mathrm{v}_2 [/math], начнем последовательно рассматривать пары соседних вершин [math] \mathrm{v}_i \mathrm{v}_{i+1} [/math], пока [math]i \ge n[/math] (Когда [math]i = n[/math], за [math]\mathrm{v}_{i+1}[/math] считаем [math]\mathrm{v}_{1}[/math]).

  • Если между ними есть ребро, то переходим к следующей паре вершин [math] \mathrm{v}_{i+1} \mathrm{v}_{i+2}[/math].
  • Если же ребра нет, то найдем такую вершину [math]\mathrm{v}_j[/math] (то, что она всегда существует, будет показано ниже), что [math] \mathrm{v}_j \in{\mathbb{V}} \setminus \{ \mathrm{v}_i, \mathrm{v}_{i+1} \} [/math], и существуют ребра [math] \mathrm{v}_i \mathrm{v}_j[/math] и [math] \mathrm{v}_{i+1} \mathrm{v}_{j+1} [/math] (Если [math] j = n[/math] , то за [math]\mathrm{v}_{j+1}[/math] считаем [math]\mathrm{v}_{1}[/math]).
    • Если [math]i \lt j [/math] то перевернем часть перестановки от [math] i+1 [/math] до [math] j [/math] (включительно).
    • Если [math] i \gt j [/math] обменяем в перестановке элементы на позициях [math] (i + 1 + k)\ \operatorname{mod}\ n [/math] и [math] (j - k +n)\ \operatorname{mod}\ n [/math], где [math]k = \overline{0, (j + n - i)\ \operatorname{div}\ 2}[/math], то есть считаем [math]\mathrm{v}_{i}...\mathrm{v}_{j}[/math] равной [math]\mathrm{v}_{i}...\mathrm{v}_{n}\mathrm{v}_{1}...\mathrm{v}_{j}[/math]. Например, если [math]n = 10, i = 8, j = 1[/math], то [math]\mathrm{v}_9 [/math] и [math]\mathrm{v}_1[/math] поменяются местами, а [math]\mathrm{v}_{10}[/math] останется на месте.

Псевдокод

 for i = 1 to n                           // перебираем все вершины перестановки [math]P[/math]
   if [math] v_i v_{i+1} \notin \mathbb{E} [/math]                         // если нет ребра между [math]v_i v_{i+1} [/math]
     for [math]v_j \in \mathbb{V} \setminus \{v_i, v_{i + 1}\}[/math]              // перебираем все остальные вершины 
       if [math]v_i v_j \in \mathbb{E}\[/math] && [math] v_{i+1} v_{j+1} \in \mathbb{E}[/math]      // если есть ребра [math]v_i v_j,\ v_{i+1} v_{j+1} [/math]
         reverse_subsequence([math]P, i+1, j[/math])  // разворачиваем часть перестановки [math]P[/math] от i+1 позиции до j
         break                           // переходим к следующей итерации внешнего for                       
       

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

На [math]k[/math]-ой итерации внешнего цикла рассматриваются вершины [math]\mathrm{v}_k \mathrm{v}_{k+1}[/math]. Возможно 2 случая:

  • между ними есть ребро, и тогда делать ничего не надо;
  • между ними ребра нет, и тогда надо найти такую вершину [math]\mathrm{v}_j[/math], что [math]\mathrm{v}_k \mathrm{v}_j, \mathrm{v}_{k+1} \mathrm{v}_{j+1} \in \mathbb{E}[/math];

Покажем, что такая вершина обязательно найдется. Пусть [math]S= \{ i| \mathrm{e}_i = \mathrm{v}_k \mathrm{v}_i \in \mathbb{E}\} \subset \{1, 2, ...,n\} \setminus \{k,k+1\} [/math] и [math]T = \{ i| f_i=\mathrm{v}_k \mathrm{v}_{i+1} \in \mathbb{E} \} \subset \{1, 2, ...,n-1\} \setminus \{k\} [/math]. Тогда [math]S \cup T \subset \{1,2,...,n\} \setminus \{k\} [/math], откуда [math]|S \cup T |\lt n[/math]. Но [math]|S|+|T| = \operatorname{deg}\ v_1 + \operatorname{deg}\ v_2 \ge n[/math] по условию теоремы Оре или теоремы Дирака, в зависимости от наших начальных условий. А значит [math]S \cap T \ne \varnothing[/math], следовательно искомая вершина обязательно найдется. Теперь заметим, что после [math]k[/math]-ой итерации внешнего цикла между всеми парами вершин [math]\mathrm{v}_{i}, \mathrm{v}_{i+1}[/math], где [math]i \le k[/math] существует ребро, а значит после [math]n[/math] итераций мы найдем цикл.

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

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

См.также