ハミルトン閉路問題

ハミルトン閉路問題（Hamiltonian Cycle Problem）とは、与えられたグラフにおいて、すべての頂点を一度だけ通って出発点に戻る路（ハミルトン閉路）が存在するかどうかを判定する問題である。名称は、1857年にこの問題を正十二面体上のパズル「ハミルトンの世界一周ゲーム(Icosian Game)」として考案した数学者ウィリアム・ローワン・ハミルトンに由来する。