Алгоритм нахождения Гамильтонова цикла в условиях теорем Дирака и Оре — различия между версиями
Ak57 (обсуждение | вклад) м (→Псевдокод) |
Ak57 (обсуждение | вклад) (→Описание алгоритма) |
||
Строка 6: | Строка 6: | ||
* Если же ребра нет, то найдем такую вершину <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>\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>i < j </tex> то перевернем часть перестановки от <tex> i+1 </tex> до <tex> j </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>n = 10, i = 8, j = 1</tex>, то <tex>\mathrm{v}_9 </tex> и <tex>\mathrm{v}_1</tex> поменяются местами, а <tex>\mathrm{v}_{10}</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> останется на месте. |
== Псевдокод == | == Псевдокод == |
Версия 19:15, 6 ноября 2013
Описание алгоритма
Алгоритм находит гамильтонов цикл в неориентированном графе , если выполняются условия теоремы Оре или выполнена теорема Дирака. Рассмотрим перестановку вершин , где . Если между каждой парой соседних вершин в перестановке существует ребро, то мы получили Гамильтонов цикл. В противном случае, начиная с пары , начнем последовательно рассматривать пары соседних вершин , пока .
- Если между ними есть ребро, то переходим к следующей паре вершин .
- Если же ребра нет, то найдем такую вершину
- Если то перевернем часть перестановки от до (включительно).
- Если обменяем в перестановке элементы на позициях и , где , то есть считаем равным . Например, если , то и поменяются местами, а останется на месте.
(то, что она всегда существует, будет показано ниже), что , и существуют ребра и (Если , то за считаем ).
Псевдокод
for i = 1 to n - 1 // перебираем все вершины перестановкиот первой до предпоследней if // если нет ребра между for // перебираем все остальные вершины if && // если есть ребра reverse_subsequence( ) // разворачиваем часть перестановки от i+1 позиции до j break // переходим к следующей итерации внешнего for |
Доказательство алгоритма
Заметим, что поскольку мы сделали нашу перестановку в виде зацикленного списка, то мы можем рассматривать перебор все пар соседних в перестановке вершин, как сдвиг указателя на начало списка. Тогда будем сдвигать указатель на нашу перестановку так, чтобы она начиналась с рассматриваемой пары
. Если теперь между первыми двумя вершинами есть ребро, то можем переходить к рассмотрению следующей пары, так как в этом случае мы ничего не делаем. Если же ребра нет, то докажем, что обязательно найдется вершина , такая что .Пусть теоремы Оре или теоремы Дирака, в зависимости от наших начальных условий. А значит , следовательно искомая вершина обязательно найдется. Поскольку каждый раз, когда у нас нет ребра между двумя обрабатываемыми вершинами, мы переворачиваем нашу последовательность так, чтобы после переворота и становились связанными ребром, то, рассмотрев все пары вершин в последовательности, мы добьемся того, что любые две соседние пары вершин будут связаны ребром, а это и значит что мы нашли цикл.
и . Тогда , откуда . Но по условию