帕尔默的算法哈密顿周期 [英] Palmer's Algorithm for Hamiltonian cycles

问题描述

在密集图​​中，我试图构建使用帕尔默的算法。不过，我需要更多的解释了这个算法，因为它不与我一起工作，当我实现它。它似乎有一个不明确的部分维基百科的解释。

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

下面的算法语句：

  

帕尔默（1997年）介绍了以下简单的算法构造一个汉密尔顿的周期在图表会议矿的条件。   任意排列的顶点成一个循环，忽略了图中邻接关系。   而周期包含连续两个顶点六和 VI + 1 不在图中相邻，执行以下两个步骤：

     

  

• 搜索索引Ĵ使得四个顶点六， VI + 1 ， VJ 和 VJ + 1 都是独特的，使得图中包含六边缘 VJ + 1 和 VJ 到 VI + 1

  

• 逆周期之间的 VI + 1 和 VJ （含）。

  

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

和做什么，他们的意思是：反周期的一部分，

？

解决方案

事实上，维基百科的描述算法的<删除>is¹是错误的。帕尔默自己的描述是

  

  

1. 步骤0排列在一个圆圈的顶点。

  

2. 步骤1.看看周围的边界，称以逆时针方向，连续不相邻的顶点，即一个缺口。如果没有差距，退出与边界上的跨越周期。否则，查找一对交叉和弦从间隙的顶点到一些其他对连续顶点，可能或可能不相邻（可能间隙2）。

        

   如果找到，（即，缺口1为好！），只需重新排列顶点的圆形秩序明显的方式让两个和弦成为边界上边缘和缝隙切换到内部。每一次我们玩这个游戏的纵横交错成功，顶点的圆形布置的边界上的一个或两个缺口是由两个边所取代。否则，重复步骤1下一个差距。

        

   继续，直到跨越周期的边界上，或直至每一个差距是坏的。

  

您需要一对路口和弦，即你需要边

  V-I＆LT;  - ＆GT; 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＆GT; 2 ，使得 v_j 紧邻 V_1 和 V_ { J + 1} 到 V_2 ，第一次出现这样的 J = 3 。现在反向 4 ... 2 在循环的一部分（在此情况下，有4至没有顶点2），得到下一个循环

  1234561 //指数周期
1246351 //顶点
 

有两对相邻neighours的（（1,2）和（4,6））。第一个指数我与 V_I 不相邻的 V_ {I + 1} 是2.扫描的第 J＆GT; 3 ，使得 v_j 紧邻 V_2 = 2 和 V_ {J + 1} 相邻 V_3 = 4 。这给了 J = 5 。现在之间的部分 V_3 和 v_5 （含），给下一个周期

  1234561 //指数周期
1236451 //顶点
 

再次， V_3 = 3 是不相邻的 v_4 = 6 ，所以 I = 3 ， J = 5 ，扭转收益率

  1234561 //指数周期
1234651 //顶点
 

现在唯一不好的就是对（v_6，V_1）=（5,1）。最小的 J＆GT; 1 ，使得 v_j 紧邻 v_6 = 5 和 V_ {J + 1} 到 V_1 = 1 是 J = 2 。现在，扭转部分来自 V_1 到 V_2 收益率

  1234561 //指数周期
2134652 //顶点
 

这是一个汉密尔顿的周期。

¹我会解决它在某一时刻。

In a "dense" graph, I am trying to construct a Hamiltonian cycle using Palmer's Algorithm. However, I need more explanation for this algorithm because it does not work with me when I implement it. It seems that there is an unclear part in Wikipedia's explanation.

I would be thankful if someone explains it more clearly or give me some links to read.

Here's the algorithm statement:

Palmer (1997) describes the following simple algorithm for constructing a Hamiltonian cycle in a graph meeting Ore's condition. Arrange the vertices arbitrarily into a cycle, ignoring adjacencies in the graph. While the cycle contains two consecutive vertices vi and vi + 1 that are not adjacent in the graph, perform the following two steps:

• Search for an index j such that the four vertices vi, vi + 1, vj, and vj + 1 are all distinct and such that the graph contains edges from vi to vj + 1 and from vj to vi + 1

• Reverse the part of the cycle between vi + 1 and vj (inclusive).

To be more specific, I do not get the part where they say: "Arrange the vertices arbitrarily into a cycle" in this case, is this right to do: 0,1,2,3,4,0

and what do they mean by: "Reverse the part of the cycle"?

解决方案

Indeed, wikipedia's description of the algorithm is¹ was wrong. Palmer's own description is

1. Step 0. Arrange the vertices in a circle.

2. Step 1. Look around the boundary, say in the counterclockwise direction, for consecutive nonadjacent vertices, i.e., a gap. If there are no gaps, quit with the spanning cycle on the boundary. Otherwise, look for a pair of crossing chords from the vertices of the gap to some other pair of consecutive vertices that may or may not be adjacent (possible gap 2).

   If found, (i.e., gap 1 was good!), simply rearrange the circular order of the vertices in the obvious way so that the two chords become edges on the boundary and the gaps are switched to the interior. Each time we play this game of criss-cross successfully, one or two gaps on the boundary of the circular arrangement of vertices are replaced by two edges. Otherwise repeat Step 1 with the next gap.

   Continue until the spanning cycle is on the boundary, or until every gap is bad.

You need a pair of crossing chords, i.e. you need edges

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

That way, by reversing the part from v_{i+1} to v_j (inclusive), you move the vertex v_j - adjacent to v_i in the graph - next to v_i in your cycle, and the vertex v_{i+1} - adjacent to v_{j+1} in the graph - is moved next to v_{j+1} in the cycle. Thus we obtain two new pairs of neighbours in the cycle that are adjacent in the graph, (v_i, v_j) and (v_{i+1}, v_{j+1}), and possibly destroy one pair of cycle-neighbours that are adjacent in the graph, (v_j, v_{j+1}). The number of pairs of cycle-neighbours that are adjacent in the graph increases by 1 or by two each step, so the algorithm terminates.

With the wrong indexing of wikipedia, moving v_j next to v_i and v_{i+1} next to v_{j+1} need not generate a new pair of cycle-neighbours that are adjacent in the graph, thus the algorithm need not terminate.

So let's play it through for your example

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

arranging it as 1426351 initially (no adjacent neighbours).

The first pair of cycle-neighbours not adjacent in the graph is (1,4) = (v_1,v_2). Scan for an index j > 2 such that v_j is adjacent to v_1 and v_{j+1} to v_2, the first such occurrence is j = 3. Now reverse the part 4...2 in the cycle (in this case, there's no vertex between 4 and 2), giving the next cycle

1234561  // index in cycle
1246351  // vertex

with two pairs of adjacent neighours ((1,2) and (4,6)). The first index i with v_i not adjacent to v_{i+1} is 2. Scan for the first j > 3 such that v_j is adjacent to v_2 = 2 and v_{j+1} adjacent to v_3 = 4. That gives j = 5. Now the part between v_3 and v_5 (inclusive), giving the next cycle

1234561  // index in cycle
1236451  // vertex

Once more, v_3 = 3 is not adjacent to v_4 = 6, so i = 3, j = 5, reversing yields

1234561  // index in cycle
1234651  // vertex

Now the only bad pair is (v_6,v_1) = (5,1). The smallest j > 1 such that v_j is adjacent to v_6 = 5 and v_{j+1} to v_1 = 1 is j = 2. Now reverse the part from v_1 to v_2 yielding

1234561  // index in cycle
2134652  // vertex

which is a Hamiltonian cycle.

¹ I'll fix it in a moment.

这篇关于帕尔默的算法哈密顿周期的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！