由來
天文學家哈密頓(William Rowan Hamilton) 提出，在一個有多個城市的地圖網路中，尋找一條從給定的起點到給定的終點沿途恰好經過所有其他城市一次的路徑。
這個問題和著名的七橋問題的不同之處在於，過橋只需要確定起點，而不用確定終點。哈密頓問題尋找一條從給定的起點到給定的終點沿 途恰好經過所有其他城市一次的路徑。
漢密爾頓迴路漢密爾頓迴路
哈密頓路徑問題在上世紀七十年代初，終於被證明是“NP完備”的。據說具有這樣性質的問題，難於找到一個有效的算法。實際上對於某些頂點數不到100的網路，利用現有最好的算法和計算機也需要比較荒唐的時間（比如幾百年）才能確定其是否存在一條這樣的路徑。
給定圖G，若存在一條迴路，經過圖中每個結點恰好一次，這條迴路稱作漢密爾頓迴路。
狄拉克定理：
漢密爾頓迴路
漢密爾頓迴路Asimple graphwith graph verticesin which eachgraph vertexhasvertex degree has aHamiltonian cycle.
翻譯過來就是：
設一個 無向圖中有 N 個節點，若所有節點的度數都大於等於 N/2，則漢密爾頓迴路一定存在。注意，“N/2” 中的除法不是整除，而是實數除法。如果 N 是偶數，當然沒有歧義；如果 N 是奇數，則該條件中的 “N/2” 等價於 “⌈N/2⌉”。
迴路的構造
證明漢密爾頓迴路存在的過程其實就是構造這條迴路的過程，分成以下幾個步驟：
任意找兩個相鄰的節點 S 和 T，在它們基礎上擴展出一條儘量長的沒有重複節點的路徑。也就是說，如果 S 與節點 v 相鄰，而且 v 不在路徑 S → T 上，則可以把該路徑變成 v → S → T，然後 v 成為新的 S。從 S 和 T 分別向兩頭擴展，直到無法擴為止，即所有與 S 或 T 相鄰的節點都在路徑 S → T 上。
若 S 與 T 相鄰，則路徑 S → T 形成了一個迴路。
若 S 與 T 不相鄰，可以構造出一個迴路。設路徑 S → T 上有 k + 2 個節點，依次為 S、 v、 v…… v和 T。可以證明存在節點 v， i ∈ [1, k)，滿足 v與 T 相鄰，且 v與 S 相鄰。證明方法也是根據鴿巢原理，既然與 S 和 T 相鄰的點都在該路徑上，它們分布的範圍只有 v∼ v這 k 個點， k ≤ N - 2，而 d(S) + d(T) ≥ N，那么可以想像，肯定存在一個與 S 相鄰的點 v和一個與 T 相鄰的點 v， 滿足 j < i。那么上面的命題也就顯然成立了。
找到了滿足條件的節點 v以後，就可以把原路徑變成 S → v→ T → v→ S，即形成了一個迴路。
現在我們有了一個沒有重複節點的迴路。如果它的長度為 N，則漢密爾頓迴路就找到了。
如果迴路的長度小於 N，由於整個圖是連通的，所以在該迴路上，一定存在一點與迴路以外的點相鄰。那么從該點處把迴路斷開，就變回了一條路徑。再按照步驟 1的方法儘量擴展路徑，則一定有新的節點被加進來。接著回到步驟 2。
1.任意找兩個相鄰的節點 S 和 T，在它們基礎上擴展出一條儘量長的沒有重複節點的路徑。也就是說，如果 S 與節點 v 相鄰，而且 v 不在路徑 S → T 上，則可以把該路徑變成 v → S → T，然後 v 成為新的 S。從 S 和 T 分別向兩頭擴展，直到無法擴為止，即所有與 S 或 T 相鄰的節點都在路徑 S → T 上。
2.若 S 與 T 相鄰，則路徑 S → T 形成了一個迴路。
3.若 S 與 T 不相鄰，可以構造出一個迴路。設路徑 S → T 上有 k + 2 個節點，依次為 S、 v、 v…… v和 T。可以證明存在節點 v， i ∈ [1, k)，滿足 v與 T 相鄰，且 v與 S 相鄰。證明方法也是根據鴿巢原理，既然與 S 和 T 相鄰的點都在該路徑上，它們分布的範圍只有 v∼ v這 k 個點， k ≤ N - 2，而 d(S) + d(T) ≥ N，那么可以想像，肯定存在一個與 S 相鄰的點 v和一個與 T 相鄰的點 v， 滿足 j < i。那么上面的命題也就顯然成立了。
找到了滿足條件的節點 v以後，就可以把原路徑變成 S → v→ T → v→ S，即形成了一個迴路。
4.現在我們有了一個沒有重複節點的迴路。如果它的長度為 N，則漢密爾頓迴路就找到了。
如果迴路的長度小於 N，由於整個圖是連通的，所以在該迴路上，一定存在一點與迴路以外的點相鄰。那么從該點處把迴路斷開，就變回了一條路徑。再按照步驟 1的方法儘量擴展路徑，則一定有新的節點被加進來。接著回到步驟 2。
