実際、ウィキペディアのアルゴリズムの説明です¹間違っていました。パーマー自身の説明は
ステップ 0. 頂点を円形に配置します。
ステップ 1. 連続する隣接していない頂点、つまりギャップがないか、反時計回りの方向で境界を調べます。隙間が無ければスパンサイクルを境に終了。それ以外の場合は、ギャップの頂点から、隣接している場合と隣接していない場合がある他の連続する頂点のペアまでの交差弦のペアを探します (ギャップ 2 の可能性)。
見つかった場合 (つまり、ギャップ 1 は良好でした!)、2 つの弦が境界上のエッジになり、ギャップが内部に切り替わるように、単純に頂点の循環順序を単純に並べ替えます。この交差ゲームを成功させるたびに、頂点の円形配置の境界にある 1 つまたは 2 つのギャップが 2 つのエッジに置き換えられます。それ以外の場合は、次のギャップでステップ 1 を繰り返します。
スパニング サイクルが境界上になるまで、またはすべてのギャップが不良になるまで続行します。
クロスコードのペアが必要です。つまり、エッジが必要です。
v_i <-> v_j
v_{i+1} <-> v_{j+1}
v_{i+1}このように、パーツを からまでv_j(両端を含む)反転することにより、頂点 (グラフ内の に隣接) をサイクル内の の隣に移動し、頂点 (グラフ内の にv_j隣接)をサイクル内の の隣に移動します。したがって、グラフ内で隣接するサイクル内の 2 つの新しい隣接ペアおよびを取得し、グラフ内で隣接するサイクル隣接ペアの1 つを破壊する可能性があります。グラフ内で隣接するサイクル近傍のペアの数は、各ステップで 1 または 2 ずつ増加するため、アルゴリズムは終了します。v_iv_iv_{i+1}v_{j+1}v_{j+1}(v_i, v_j)(v_{i+1}, v_{j+1})(v_j, v_{j+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ます。最初に出現するのはです。サイクル内のパーツを逆にします (この場合、4 と 2 の間に頂点はありません)。次のサイクルを指定します。v_jv_1v_{j+1}v_2j = 34...2
1234561 // index in cycle
1246351 // vertex
隣接する 2 つのペア ((1,2)および(4,6))。iに隣接しv_iない最初のインデックスは 2 です。に隣接し、隣接する最初のインデックスをv_{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)です。とに隣接する最小j > 1のそのようなものはです。からの部分を降伏に反転しますv_jv_6 = 5v_{j+1}v_1 = 1j = 2v_1v_2
1234561 // index in cycle
2134652 // vertex
これはハミルトニアンサイクルです。
¹ すぐに修正します。