3

在“密集”图中，我正在尝试使用Palmer's Algorithm构建哈密顿循环。但是，我需要对这个算法进行更多解释，因为当我实现它时它对我不起作用。维基百科的解释似乎有一个不清楚的部分。

如果有人更清楚地解释它或给我一些阅读链接，我将不胜感激。

这是算法语句：

Palmer (1997) 描述了以下简单算法，用于在满足 Ore 条件的图中构造哈密顿循环。将顶点任意排列成一个循环，忽略图中的邻接关系。当循环包含两个连续的顶点vi并且vi + 1在图中不相邻时，执行以下两个步骤：

  • 搜索一个索引j，使得四个顶点vi、vi + 1、vj和vj + 1都是不同的，并且图包含从vitovj + 1和 from vjto的边vi + 1

  • vi + 1反转和vj（包括）之间的循环部分。

更具体地说，我没有得到他们说的部分：在这种情况下，“将顶点任意排列成一个循环”，这是正确的做法：0,1,2,3,4,0

它们是什么意思：“扭转循环的一部分”？

4

2 回答 2

1

在这种情况下，是否有权这样做：0,1,2,3,4,0

是的。通过从更仔细选择的初始循环开始，您可能会获得更快的解决方案，但是只要图形满足 Ore 的条件，算法将从任何有效的初始循环开始成功。

它们是什么意思：“扭转循环的一部分”？

这意味着采用从 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

这是Palmer 论文的链接（参见 Wikipedia 中的参考部分）。

于 2012-06-30T12:31:28.720 回答
1

确实，维基百科对算法的描述是¹错了。帕尔默自己的描述是

  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 或 2，因此算法终止。

由于维基百科的错误索引，移动v_jnextv_i和v_{i+1}nextv_{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是。现在反转循环中的部分（在这种情况下，在 4 和 2 之间没有顶点），给出下一个循环v_jv_1v_{j+1}v_2j = 34...2

1234561  // index in cycle
1246351  // vertex

有两对相邻的邻居 ((1,2)和(4,6))。不相邻的第一个索引是 2。扫描第一个与i相邻和相邻的索引。这给了. 现在和（含）之间的部分，给出下一个循环v_iv_{i+1}j > 3v_jv_2 = 2v_{j+1}v_3 = 4j = 5v_3v_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). 与和to相邻的最小j > 1的是。现在将零件从屈服反转v_jv_6 = 5v_{j+1}v_1 = 1j = 2v_1v_2

1234561  // index in cycle
2134652  // vertex

这是一个哈密顿循环。

¹我会马上修复它。

于 2012-07-20T13:53:45.353 回答