在圖論中，哈密顿路径（）是在無向圖或有向圖中，恰好能將圖中所有頂點各拜訪一次的路徑。與之相近的概念為哈密顿环（），即該路徑在拜訪完圖中所有頂點後會回到出發點，而構成一個環。要確定圖中是否存在哈密顿路徑或哈密顿環的問題稱為哈密顿路径问题，這個問題是一個NP完全的問題。哈密顿路徑有時會跟尤拉路徑一起討論，因為哈密顿路徑要求通過所有頂點（哈密顿路径问题）而尤拉路徑要求通過所有邊（一筆畫問題）。
定義
哈密顿路徑是一個拜訪過某圖所有頂點的路徑，且每個頂點只會被拜訪一次。存在哈密顿路徑的圖稱為可追蹤圖。如果一個圖中每對頂點都能找到一條哈密顿路徑，則這個圖可以被視為哈密顿連通的。哈密顿環或哈密顿迴路是一個拜訪過某圖所有頂點的環或循環路徑，在這個循環路徑中每個頂點只會被拜訪一次，且拜訪完所有頂點後會回到起始點。存在哈密顿環的圖稱為哈密顿圖。哈密顿環與哈密顿路徑主要可以由起點和終點來區別：若一哈密顿路徑起點與終點相同，其為哈密顿環；而若起點與終點不同，則其就不是哈密顿環，僅能視為哈密顿路徑。
是將圖分解成哈密顿環的邊分解方式。
哈密顿迷宮是一種邏輯益智遊戲，其目標在於找到圖中唯一的哈密顿環。
性質
任何哈密顿環都可以透過移除一條邊來轉換成哈密顿路徑。然而哈密頓路徑只有路徑的2端點相鄰時才有機會透過新增一條邊來轉換成哈密顿環。所有具備哈密顿環的圖（即哈密顿圖）都是雙連通圖；但雙連通圖不一定會存在哈密顿環（即雙連通圖不一定是哈密顿圖，如佩特森圖）。
階數為n（n=1,2,3...）的簡單圖中存在的哈密顿環的總數為0, 0, 2, 10, 58, 616, 9932, 333386, 25153932, 4548577688, ...。
參見
*哈密顿图：具有哈密顿環的圖
*哈密顿路径问题：判斷圖中是否存在哈密顿路徑的問題
參考文獻
外部連結
*
- [https://web.archive.org/web/20120309190309/http://www.graph-theory.net/euler-tour-and-hamilton-cycles/ Euler tour and Hamilton cycles]
评论 (0)