ハミルトニアンサイクル、検証と発見

Question

グラフ G にハミルトニアン サイクルがあるかどうかを多項式時間で判断するアルゴリズムがある場合、多項式時間でハミルトニアン サイクルを見つけるアルゴリズムは存在できるでしょうか?

私の試みは、グラフ G のエッジを削除して G' を持たせることです。G' でアルゴリズムを実行した後、ハミルトニアン サイクルがあるかどうかを確認します。そうでない場合は、エッジが何らかのハミルトニアン サイクル内にあることを意味します。今、どうやって続ければいいのかわかりません。

Answer 1

させて $P$ グラフ内の任意の単純なパスになります。もし $P$ グラフのハミルトニアン サイクルに現れる場合は、すべての頂点を削除できます。 $p$ 最初と最後の頂点を除いて、これら 2 つの頂点をエッジで接続すると、結果のグラフはハミルトニアンになる必要があります。

これを念頭に置いて、長さ 1 のパスから始めて段階的にハミルトニアン サイクルを構築できます。そのようなパスの構築方法はすでに説明したためです。次に、ある長さのパスを延長できます $i$ 長い道に $i+1$ 上記のトリックを使用して、パス内の最後の頂点のすべての近傍を次の頂点として試し、上記のトリックを適用して、新しいパスがサイクルの一部であるハミルトニアン サイクルが存在するかどうかを確認します。せいぜいブラックボックスと呼ぶことに注意してください $m := |E|$ 回。ある程度の長さの道に到達したら $n-3$ ハミルトン サイクルへのパスを線形時間で完了するのは簡単です。