ハミルトン閉路問題のソースを表示

'''ハミルトン閉路問題'''（ハミルトンへいろもんだい）とは、与えられた[[グラフ理論|グラフ]]について、全ての[[頂点]]を一度だけ通る[[閉路]]が存在するかどうか調べる問題である。名称はこの問題を最初に研究した数学者[[ウィリアム・ローワン・ハミルトン]]の名に因む

== 概要 ==
与えられたグラフが有向グラフ（[[グラフ理論]]参照）の場合は'''有向ハミルトン閉路問題'''、無向グラフ（通常のグラフ）の場合は'''無向ハミルトン閉路問題'''と呼ばれる。

この問題はどちらも、[[NP完全問題]]であることが知られている。また、無向ハミルトン閉路問題は[[巡回セールスマン問題]]の特殊ケースでもある。

始点と終点が一致するという閉路の条件を取り去ると、[[ハミルトン路]]問題になる。

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

{{DEFAULTSORT:はみるとんへいろもんたい}}
[[Category:グラフ理論]]
[[Category:数学の問題]]
[[Category:数学に関する記事]]
{{sci-stub}}