1 2 3 4 5 6 7 8 9 10 11 12 Contents
相較於尤拉迴圈是指一條通過圖中所有「邊」的封閉路徑，哈米爾頓迴圈（Hamiltonian circuit）是指一條通過圖中所有「點」的封閉路徑。這個名稱據說是因為愛爾蘭數學家哈米爾頓在1867年發明了一種環遊世界的遊戲：在正十二面體的二十個頂點填入20個都市，如倫敦、紐約……等，然後讓玩家任意由一個都市出發，在不重覆經過同一都市的條件下走完全部的都市並回到起點。若考慮一個只有“骨架”的正十二面體，我們可以得到下面的圖：
環遊世界的遊戲說穿了就是要在上圖中找一個哈米爾頓迴圈。
不像尤拉迴圈的有在性問題那麼明確，決定一個圖中是否存在哈米爾頓迴圈是非常困難的問題。僅管圖論學家一百多年來不斷地努力，目前我們只知道存在哈米爾頓迴圈的充分條件。
如果一個圖G中存在哈米爾頓迴圈的話，我們可以去掉幾條邊，而得到一個較小的圖H，圖H具有以下性質：
H的點就是G的點；
H是連通的；
H中的邊數與點數一樣多；
H中的點的秩都是2。
下圖是否存在哈米爾頓迴圈呢？
若此圖中存在哈米爾頓迴圈，我們知道藉由去掉幾條邊，則可以得到一個具有上述的四個性質的圖, H。點a, c, d, e的秩都是2——滿足性質4，但是點b的秩是4，所以我們需要把b的邊去掉兩條。然而，若去掉{a, b}邊的話，a的秩就會變成1；去掉{b, c}邊的話，c的秩就會變成1；{b, d}, {b, e}邊也都是同樣的情況。這表示我們永遠沒辦法滿足性質4，所以此圖中不存在哈米爾頓迴圈。
什麼樣的圖中會存在哈米爾頓迴圈？
直覺上，如果每個點的秩夠大的話，則圖中存在哈米爾頓迴圈的機會就比較大。1952年Dirac證明了下面的定理：
「一個點數大於等於3的簡單圖，
如果每個點的秩都大於等於點數的一半，
則這個圖中有哈米爾頓迴圈。」
註：所謂簡單圖，就是圖中的任兩點間最多只有一條邊，而且圖中沒有兩端接在同一點的邊。
完全圖是一個極端的例子：
n個點的完全圖，因為任兩點都有邊相連，圖中每個點的秩均為n-1。由Dirac定理，我們知道圖中一定存在哈米爾頓迴圈；大家不難發現其實圖中存在許多哈米爾頓迴圈 —— 一共有
個不同的哈米爾頓迴圈。
下面是4個點的完全圖，你能找出3個不同的哈米爾頓迴圈嗎？
註：A－B－C－D－A和A－D－C－B－A是視為相同的迴圈。
以下這些圖是否存在一條封閉路徑（起點和終點為同一點），並通過每一個點恰好一次？如果有的話，你能找出這條路徑嗎？
