ハミルトン路

ウィキペディア

ハミルトン路

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2024/04/19 05:20 UTC 版)

ハミルトン路（ハミルトンろ、英語: Hamiltonian path）とは、グラフ上の全ての頂点を 1 度ずつ通る路のこと。特に、グラフ上の全ての頂点を 1 度ずつ通る閉路はハミルトン閉路という。また、ハミルトン閉路を含むグラフのことをハミルトングラフといい、ハミルトン路は含むがハミルトン閉路は含まないようなグラフのことを準ハミルトングラフという。