哈密頓路徑 -- 來自

哈密頓路徑，也稱為 Hamilton path，是圖路徑，位於圖的兩個頂點之間，並且恰好訪問每個頂點一次。如果存在端點相鄰的哈密頓路徑，則生成的圖環稱為哈密頓環（或 Hamiltonian cycle）。

擁有哈密頓路徑的圖稱為可追蹤圖。

一般來說，找到哈密頓路徑的問題是 NP-完全的 (Garey and Johnson 1983, pp. 199-200)，因此確定給定通用圖是否具有哈密頓路徑的唯一已知方法是進行窮舉搜尋

任何頂點奇偶性不平衡的二分圖都沒有哈密頓路徑。

在 Wolfram 語言中，實現了查詢圖的單個哈密頓路徑，命令如下：FindHamiltonianPath[g]。可以使用以下命令（效率低下）找到給定圖的所有哈密頓路徑：HamiltonianPath[g,All] 在 Wolfram 語言包中Combinatorica`。可以使用以下命令獲得許多命名圖的所有哈密頓路徑的預計算列表：GraphData[graph,"HamiltonianPaths"]，其中包含路徑的兩個方向（因此 1, 2, 3 被認為與 3, 2, 1 不同）。哈密頓路徑的相應數量的預計算計數由以下命令給出：GraphData[graph,"HamiltonianPathCount"].

對於階數 , 2, ... 的所有簡單圖，有向哈密頓路徑的總數分別為 0, 2, 8, 50, 416, 5616, 117308, 4862736, ... (OEIS A193352)。

Rubin (1974) 描述了一種高效的搜尋程式，可以使用大大減少回溯和猜測的推導來查詢圖中的某些或所有哈密頓路徑和環路。Wilf (1994) 描述的 Angluin 和 Valiant (1979) 提出的機率演算法也可能有助於查詢哈密頓環和路徑。如果哈密頓環的演算法可用，則可以找到兩個頂點和之間的哈密頓路徑。這可以透過檢查原始圖是否包含邊，如果不存在則新增它以獲得來完成。由於具有相鄰端點的哈密頓路徑是哈密頓環，並且由於和現在相鄰，因此找到哈密頓環並在邊處分割會得到從到在中的哈密頓路徑。同樣，如果中不存在哈密頓環，則中沒有從到的哈密頓路徑。