在“密”图形，我试图构建使用哈密顿圈帕尔默的算法 。 不过，我需要更多的解释了这种算法，因为当我实现它不和我一起工作。 它似乎有在维基百科的解释不明确的部分。
如果有人解释得更清楚或给我一些链接，阅读，我会感激。
这里的算法语句：
帕尔默（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
“反周期的一部分”：和他们怎么用呢？
事实上， 维基百科的描述算法 is¹ 错了。 帕尔默自己的描述是
步骤0排列在一个圆的顶点。
步骤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
用两对相邻的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
这是一个汉密尔顿的周期。
¹我将在稍后解决它。
在这种情况下，这是正确的事：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
这里是一个链接帕尔默的纸张 （参见维基百科中的参考部分）。
