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

Материал из Викиконспекты
Перейти к: навигация, поиск
м
м
Строка 33: Строка 33:
 
<tex>\subset  \{2, 3, ...,n-1\}</tex>.
 
<tex>\subset  \{2, 3, ...,n-1\}</tex>.
 
Тогда <tex>S \cup T \subset \{2,3,...,n\}</tex>, откуда <tex>|S \cup T |< n</tex>. Но <tex>|S|+|T| = deg v_1 + deg v_2 >=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| = deg v_1 + deg v_2 >=n</tex> по условию [[Теорема Оре|теоремы Оре]] или [[Теорема Дирака|теоремы Дирака]], в зависимости от наших начальных условий. А значит <tex>S \cap T \ne \varnothing</tex>, следовательно искомая вершина обязательно найдется.
Поскольку каждый раз, когда у нас нет ребра между двумя обрабатываемыми вершинами, мы переворачиваем нашу последовательность так, чтобы после переворота <tex>\mathrm{v}_i, \mathrm{v}_{i+1}</tex> и <tex>\mathrm{v}_j, \mathrm{v}_{j+1}</tex> становились связанными ребром, то, рассмотрев, все пары вершин в последовательности, мы добьемся того, что любые две соседние пары вершин <tex>\mathrm{v}_i, \mathrm{v}_{i+1}</tex> будут связаны ребром, а это и значит что мы нашли цикл.
+
Поскольку каждый раз, когда у нас нет ребра между двумя обрабатываемыми вершинами, мы переворачиваем нашу последовательность так, чтобы после переворота <tex>\mathrm{v}_i, \mathrm{v}_{i+1}</tex> и <tex>\mathrm{v}_j, \mathrm{v}_{j+1}</tex> становились связанными ребром, то, рассмотрев все пары вершин в последовательности, мы добьемся того, что любые две соседние пары вершин <tex>\mathrm{v}_i, \mathrm{v}_{i+1}</tex> будут связаны ребром, а это и значит что мы нашли цикл.

Версия 19:01, 7 октября 2013

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

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

Если между ними есть ребро, то переходим к следующей паре вершин [math] \mathrm{v}_{i+1} \mathrm{v}_{i+2}[/math].

Если же ребра нет, то найдем такую вершину [math]\mathrm{v}_j[/math], что [math] \mathrm{v}_j \in{\mathbb{G}} \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]i+1 [/math] до [math] j [/math] (считаем, что наша перестановка зациклиный список). Например, если [math]n = 10, i = 8, j = 1[/math], где [math]n = | \mathbb{V} |[/math], то [math]\mathrm{v}_9 [/math] и [math]\mathrm{v}_1[/math] поменяются местами, а [math]\mathrm{v}_{10}[/math] останется на месте.


Псевдокод

 for(int i = 1; i < n; i++)              //перебираем все пары соседних вершин в перестановке
   if ([math] v_i v_{i+1} \in \mathbb{G} [/math])                      //если есть ребро
     continue;                          //переходим к следующей паре 
   else                                 //иначе
     while([math] v_j \in \mathbb{G} \setminus \{v_i , v_{i+1} \}[/math])          //перебираем все вершины
       if ([math]v_i v_j \notin \mathbb{E}\ \mid \mid v_{i+1} v_{j+1} \notin \mathbb{E}[/math])   //если есть ребра [math]v_i v_j,\ v_{i+1} v_{j+1} [/math]
         swap([math] i+1, j+1[/math]);             //разворачиваем нужную часть перестановки
         continue;                      //переходим к следующей паре вершин  
       

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

Заметим, что поскольку мы сделали нашу перестановку в виде зацикленного списка, то мы можем рассматривать перебор все пар соседних в перестановке вершин, как сдвиг указателя на начало списка. Тогда будем сдвигать указатель на нашу перестановку так, чтобы она начиналась с рассматриваемой пары [math]\mathrm{v}_i \mathrm{v}_{i+1}[/math]. Если теперь между первыми двумя вершинами есть ребро, то можем переходить к рассмотрению следующей пары, так как в этом случае мы ничего не делаем. Если же ребра нет, то докажем, что обязательно найдется вершина [math] \mathrm{v}_j \in \mathbb{V} \setminus \{\mathrm{v}_1, \mathrm{v}_{2}\}[/math], такая что [math]\mathrm{v}_1 \mathrm{v}_j,\ \mathrm{v}_2 \mathrm{v}_{j+1} \in \mathbb{E} [/math].

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