Алгоритм Палмера для гамильтоновых циклов

Question

В «плотном» графе я пытаюсь построить гамильтонов цикл, используя Palmer's Algorithm. Однако мне нужно больше объяснений для этого алгоритма, потому что он не работает со мной, когда я его реализую. По-видимому, в объяснении Википедии есть неясная часть.

Буду признателен, если кто-нибудь объяснит это более четко или даст мне некоторые ссылки для чтения.

Вот утверждение алгоритма:

Palmer (1997) описывает следующий простой алгоритм построения гамильтонова цикла в графе встречи условие Оре. Устройте вершины произвольно в цикл, игнорируя примыкания в графе. В то время как цикл содержит два последовательных вершин vi и vi + 1, которые не являются смежными в графе, выполняют следующие два шага:

• Поиск по индексу j таким образом, что четыре вершины vi, vi + 1, vj, и vj + 1 все различны и такие, что граф содержит ребро от vi до vj + 1 и от vjvi + 1 к

• Reverse части цикла между vi + 1 и vj (включительно).

Чтобы быть более конкретным, я не получаю ту часть, где они говорят: «Упорядочить вершины произвольно в цикл» в данном случае, это право делать: 0,1,2 , 3,4,0

И что они означают: «Изменить часть цикла»?

Answer 1

Действительно, wikipedia's description из алгоритма is¹ был не прав. собственное описание Палмер является

1. Шаг 0. Упорядочить вершины по кругу.

2. Шаг 1. Осмотрите границу, скажем в направлении против часовой стрелки, для последовательных несмежных вершин, т. Е. Зазора. Если нет пробелов, прекратите цикл spanning на границе. В противном случае найдите пару пересекающихся аккордов из вершин щели в другую пару последовательных вершин, которые могут быть или не быть смежными (возможный зазор 2).

   Если найдено (т. Е. Зазор 1 был хорошим!), Просто измените круговой порядок вершин очевидным образом, чтобы эти два аккорда стали ребрами на границе, а промежутки переключались во внутреннее пространство. Каждый раз, когда мы успешно играем в эту игру criss-cross, один или два пробела на границе кругового расположения вершин заменяются двумя ребрами. В противном случае повторите шаг 1 со следующим зазором.

   Продолжайте, пока цикл охвата не будет находиться на границе, или пока каждый зазор не станет плохим.

Вам нужна пара пересечения аккорда, то есть вам нужны кромки

v_i <-> v_j 
v_{i+1} <-> v_{j+1} 

Таким образом, при движении заднего хода части от v_{i+1} до v_j (включительно), при перемещении вершины v_j - рядом с v_i на графике - рядом с v_i в вашем цикле, а вершина v_{i+1} - рядом с v_{j+1} на графике - перемещается рядом с v_{j+1} в цикле. Таким образом, мы получаем две новые пары соседей в цикле, которые смежны на графике, (v_i, v_j) и (v_{i+1}, v_{j+1}), и, возможно, уничтожают пару соседних по циклу соседей цикла, которые смежны на графике, (v_j, v_{j+1}). Число пар соседних в графе циклов-соседей увеличивается на 1 или два на каждом шаге, поэтому алгоритм завершается.

С неправильной индексации википедии, перемещаясь v_j рядом с полем v_i и v_{i+1} рядом с полем v_{j+1} не нужно генерировать новую пару циклов-соседей, которые являются смежными в графе, таким образом, алгоритм не нужно прекратить.

Итак, давайте играть через для примера

E = { (1,2), (1,3), (1,6), (3,2), (3,4), (5,2), (5,4), (6,4), (6,5) } 

устраивая как 1426351 изначально (не смежных соседей).

Первая пара соседних по циклу соседних по графику точек - (1,4) = (v_1,v_2). Сканируйте индекс j > 2, так что v_j находится рядом с v_1 и v_{j+1} до v_2, первым из которых является j = 3.Теперь обратная часть 4...2 в цикле (в данном случае, не существует вершин между 4 и 2), что дает следующий цикл

1234561 // index in cycle 
1246351 // vertex 

с двумя парами соседних neighours ((1,2) и (4,6)). Первый индекс i с v_i, не являющийся смежным с v_{i+1}, является 2. Сканирует первый j > 3 так, что v_j находится рядом с v_2 = 2 и v_{j+1}, смежными с v_3 = 4. Это дает j = 5. Теперь часть между v_3 и v_5 (включительно), что дает следующий цикл

1234561 // index in cycle 
1236451 // vertex 

Еще раз v_3 = 3 не смежна с v_4 = 6, так i = 3, j = 5, реверсивные дает

1234561 // index in cycle 
1234651 // vertex 

теперь только плохие пара - (v_6,v_1) = (5,1). Самый маленький j > 1 такой, что v_j находится рядом с v_6 = 5 и v_{j+1} до v_1 = 1 - j = 2. Теперь обратный часть от v_1 к v_2 получая

1234561 // index in cycle 
2134652 // vertex 

который является гамильтонов цикл.

¹ Я исправлю это через мгновение.

Answer 2

в данном случае, это право делать: 0,1,2,3,4,0

Да. Вы можете получить более быстрое решение, начиная с более тщательно выбранного начального цикла, однако алгоритм будет успешным, начиная с любого действительного начального цикла, при условии, что график удовлетворяет условию Оре.

И что они подразумевают под: «Изменить часть цикла»?

Это означает, что по пути от Vi + 1, VJ и повернуть его вспять, так что если вы начали с:

vi, vi + 1, vi + 2, vj - 2, vj - 1, vj, vj + 1 

вы в конечном итоге с:

vi, vj, vj - 1, vj - 2, vi + 2, vi + 1, vj + 1 

так, что в вашем Например, если мы выберем i = 0 и j = 3, конечным результатом будет:

0, 3, 2, 1, 4, 0 

H ere является ссылкой на Palmer's paper (см. справочный раздел в Википедии).