哈密頓圖

[Hamilton cycle]

圖的哈密頓圈是指包含圖的所有頂點的圈。類似地，包含圖的所有頂點的路稱為圖的哈密頓路（Hamilton path）。一個圖若包含哈密頓圈，則稱這個圖為哈密頓圖（Hamiltonian graph）。這種路和圈之所以用哈密頓的名字命名，是因為哈密頓在1856年發明了正 12 面體數學遊戲：從正 12 面體的一個頂點出發沿稜行走，能否經過每一個頂點恰好一次回到出發點。用圖的語言即為：給定一個圖G，G是否有哈密頓圈。

與歐拉圖的情形不同，還未找到判斷一個圖是否是哈密頓圖的非平凡的充要條件。事實上這是圖論中尚未解決的主要問題之一。哈密頓圖有很多充分條件，例如，

（1）若圖的最小度不小於頂點數的一半，則圖是哈密頓圖；

（2）若圖中每一對不相鄰的頂點的度數之和不小於頂點數，則圖是哈密頓圖。

另外，還有很多用度序列、度和、圖的堅韌度等參數給出的充分條件。 ^[2] 

定理1： 設無向圖G是哈密頓圖，V₁是V的任意的非空子集， p(G-V₁)≤|V₁| 其中，p(G-V₁)為從G中刪除V₁(刪除V₁中各頂點及關聯的邊)後所得到的圖的連通分支。

定理2： 設G是n(n≥3)階無向簡單圖，如果G中任何一對不相鄰的頂點度數之和都大於等於n，則G是哈密頓圖。

定理3： 在n(n≥2)階有向圖D=中，如果所有有向邊均用無向邊代替，所得無向圖中含生成子圖K_n，則有向圖中存在哈密頓圖。

定理4：設G=(,E)是無向圖,若G沒有哈密頓圈,但對任意兩個不相鄰的頂點和,聯結一邊後的圖G+u,0是哈密頓的,則稱G為極大非哈密頓圖。 ^[3] 

推論： n(n≥3)階有向完全圖為哈密頓圖。

哈密頓路徑也稱作哈密頓鏈，指在一個圖中沿邊訪問每個頂點恰好一次的路徑。尋找這樣的一個路徑是一個典型的NP-完全(NP-complete）問題。後來人們也證明了，找一條哈密頓路的近似比為常數的近似算法也是NP完全的。

一般地，尋找一個圖的哈密頓圈問題是 NP 困難的。因此通常都是用窮舉搜索的方法來判定一個圖是否含有哈密頓路或圈。後來魯賓（F.Rubin）利用推演的方法給出了一個好一點的搜索步驟來找出圖裏的一些或者全部的哈密頓路或圈，安格魯因（D.Angluin）和瓦利安特（L.G.Valiant）設計的概率算法對哈密頓路或圈的尋找也是非常有用的。尋找哈密頓路的確定算法雖然很難有多項式時間的，但是這並不意味着只能進行時間複雜度為

暴力搜索。利用狀態壓縮動態規劃，我們可以將時間複雜度降低到

，具體算法是建立方程f[i][S][j]，表示經過了i個節點，節點都是集合S的，到達節點j時的最短路徑。每次我們都按照點j所連的節點進行轉移。

哈密頓圖及其判定方法可以解決中國郵路問題、旅行售貨員問題、排座位問題、判定圖是否可一筆畫問題。 ^[1]