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

Question

В "плотном" графе я пытаюсь построить гамильтонов цикл с использованием алгоритма Палмера. Однако мне нужно больше объяснений для этого алгоритма, потому что он не работает со мной, когда я его реализую. Кажется, в объяснении Википедии есть неясная часть.

Я был бы благодарен, если бы кто-то объяснил это более ясно или дал мне несколько ссылок для чтения.

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

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

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

• Обратный часть цикла между vi + 1 а также vj (Включительно).

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

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

Answer 1

Действительно, описание алгоритма из Википедии is¹ был неправ. Собственное описание Палмера

1. Шаг 0. Расположите вершины по кругу.

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

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

с двумя парами соседних соседей ((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

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

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

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

Вот ссылка на статью Палмера (см. Справочный раздел в Википедии).