hamiltonian-cycle - 立方平面グラフでハミルトニアン サイクルを見つける

Question

比較的小さい (40 ～ 80 ノード) 立方 (3-正則) 平面グラフがあり、それらのハミルトニシティを決定する必要があります。このタスクが NP 完全であることは認識していますが、関心のあるグラフ サイズに対して非常に高速な漸近指数時間アルゴリズムを期待しています。

Answer 1

40ノードは実行可能のようです。含めるエッジ 60 個のうち 40 個を選択しています。

深さ優先検索を試してみましょう。

まず、頂点 V を選択します。その 3 つのインシデント エッジのうち 1 つだけを除外する必要があります。これらの 3 つの可能性を 1 つずつ試してください。除外するエッジを選択すると、4 つのエッジを強制的に含めることになります。この後、除外されたエッジの頂点を「使用済み」と呼びます。

このプロセスを 10 回繰り返すことができれば、3^10 (59049) の可能性のみを検索して、40 個のエッジすべてを選択したことになります。もちろん、十分なエッジが決定されると、「孤立した」頂点がなくなります。

しかし、今ではアルゴリズムのアイデアがあります。各ステップで、「使用された」近傍が最も少ない頂点を選択してみてください。実際には、使用されたエッジが強制されるため、2 つの隣接する頂点を選択するのが最適です。使用されている隣接点が 1 つまたは 0 の頂点を選択することが次善の策かどうかはわかりません。両方の方法を試してください！(そして、3 つの使用されたネイバーは検索の失敗を示します)

エッジの選択が完了したら、単一のサイクルを形成するかどうかを確認します。

いくつかのサンプル グラフはありますか? 簡単な実装を試すかもしれません。

Answer 2

http://mathworld.wolfram.com/HamiltonianCycle.htmlより: 「Rubin (1974) は、バックトラッキングと当て推量を大幅に削減する演繹法を使用して、グラフ内のハミルトン パスと回路の一部またはすべてを見つけることができる効率的な検索手順について説明しています。」

論文はこちらで販売されています: http://portal.acm.org/citation.cfm?id=321850.321854