ハミルトン閉路問題
与えられたgraphに、ハミルトン閉路が存在するかどうかを判定する問題
NP完全問題
クラスNPに属す
存在するかどうかを示すのは難しいが、ハミルトン閉路を一つでも示されれば検証は容易
巡回セールスマン問題の特殊ケース
有向ハミルトン閉路問題と無向ハミルトン閉路問題がある
ハミルトン閉路問題を解く方法は、
どんなに工夫をしても、その手間がグラフの起きさに対して指数関数的に増加するような効率の悪いものしか無い
と考えられている
関連
ディラックの定理
オーレの定理
オイラー閉路問題
参考
数理勢の知らないグラフ理論2:ハミルトン閉路 - okunoin’s blog