text: 在圖論中，#重定向 是在無向圖或有向圖中，恰好能將圖中所有頂點各拜訪一次的路徑。與之相近的概念為#重定向 ，即該路徑在拜訪完圖中所有頂點後會回到出發點，而構成一個環。要確定圖中是否存在哈密頓路徑或哈密頓環的問題稱為哈密頓路徑問題，這個問題是一個NP完全的問題。哈密頓路徑有時會跟尤拉路徑一起討論，因為哈密頓路徑要求透過所有頂點。:218定義.哈密頓路徑是一個拜訪過某圖所有頂點的路徑，且每個頂點只會被拜訪一次。存在哈密頓路徑的圖稱為可追蹤圖。如果一個圖中每對頂點都能找到一條哈密頓路徑，則這個圖可以被視為哈密頓連通的。哈密頓環或哈密頓迴路是一個拜訪過某圖所有頂點的環或迴圈路徑:196，在這個迴圈路徑中每個頂點只會被拜訪一次，且拜訪完所有頂點後會回到起始點。存在哈密頓環的圖稱為哈密頓圖。哈密頓環與哈密頓路徑主要可以由起點和終點來區別：若一哈密頓路徑起點與終點相同，其為哈密頓環；而若起點與終點不同，則其就不是哈密頓環，僅能視為哈密頓路徑。是將圖分解成哈密頓環的邊分解方式。哈密頓迷宮是一種邏輯益智遊戲，其目標在於找到圖中唯一的哈密頓環。性質.任何哈密頓環都可以透過移除一條邊來轉換成哈密頓路徑。然而哈密頓路徑只有路徑的2端點相鄰時才有機會透過新增一條邊來轉換成哈密頓環。所有具備哈密頓環的圖。階數為n。
metadata: erhwenkuo/wikipedia-zhtw
metadata: 哈密頓路徑
metadata: https://zh.wikipedia.org/wiki?curid=7633190