主题:科學/特选图片/12維基百科,自由的 encyclopedia 哈密顿路徑是無向圖的一條路徑,這路徑经过無向圖的所有节点且只经过一次。寻找哈密顿路径的問題稱為哈密頓路徑問題,是因物理学家威廉·哈密顿提出而命名。哈密頓路徑問題是一个典型的NP-完全问题。后来人们也证明了,找一条哈密顿路的近似也是NP-完全問題。 正十二面體的哈密顿路径顯示於其施萊格爾圖(Schlegel diagram)。
哈密顿路徑是無向圖的一條路徑,這路徑经过無向圖的所有节点且只经过一次。寻找哈密顿路径的問題稱為哈密頓路徑問題,是因物理学家威廉·哈密顿提出而命名。哈密頓路徑問題是一个典型的NP-完全问题。后来人们也证明了,找一条哈密顿路的近似也是NP-完全問題。 正十二面體的哈密顿路径顯示於其施萊格爾圖(Schlegel diagram)。