ハミルトン閉路問題
ハミルトン閉路問題は NP完全問題の頂点被覆問題が有向ハミルトン閉路問題に多項式時間変換可能であることが証明され、さらに有向ハミルトン閉路問題は無向ハミルトン閉路問題に多項式変換可能であることが証明できることで、NP完全問題であると証明された。
表示
編集