ハミルトン路とは、グラフ上の全ての頂点を 1 度ずつ通る路のこと。特に、グラフ上の全ての頂点を 1 度ずつ通る閉路はハミルトン閉路という。また、ハミルトン閉路を含むグラフのことをハミルトングラフといい、ハミルトン路は含むがハミルトン閉路は含まないようなグラフのことを準ハミルトングラフという。与えられたグラフがハミルトン路を含むかどうか判定する問題は、NP完全。与えられたグラフがハミルトングラフかどうか判定する問題については、ハミルトン閉路問題を参照のこと。

出典:wikipedia