与えられた無向グラフ G、ハミルトニアン パスとハミルトン サイクルが互いに可約な多項式時間であることを示す必要があります。これが私の還元ですが、これは正しいですか？
サイクルからパスの場合 V に属する頂点 v の場合、頂点 v' を追加し、すべての e(v,u) に対してエッジ e(v' ,u) を追加します。v から v' へのハミルトニアン パスが存在する場合、v のハミルトニアン サイクルが存在します。
頂点 s および t の場合、すべてのエッジ e(t,u) に対してエッジ e(s,u) を追加し (このエッジが存在しない場合)、すべてのエッジ e(s,u) に対して endge を追加します。 (t,u) (このエッジが存在しない場合)。最後にエッジ e(s,t) を追加します。s または t にハミルトニアン サイクルがある場合、s から t へのハミルトニアン パスが存在します。
削減は正しいですか？また、これは、これら 2 つの問題が多項式時間で相互に還元可能であることを示すのに十分ですか?