基本介紹
- 中文名：哈密頓圖
- 外文名：Hamiltonian graph
- 國家：美國
- 時間：1960年
- 學科：數學
- 套用：算法、路徑問題
哈密頓圈,判斷條件,算法級別,
哈密頓圈
[Hamilton cycle]
圖的哈密頓圈是指包含圖的所有頂點的圈。類似地，包含圖的所有頂點的路稱為圖的哈密頓路（Hamilton path）。一個圖若包含哈密頓圈，則稱這個圖為哈密頓圖（Hamiltonian graph）。這種路和圈之所以用哈密頓的名字命名，是因為哈密頓在1856年發明了正 12 面體數學遊戲：從正 12 面體的一個頂點出發沿棱行走，能否經過每一個頂點恰好一次回到出發點。用圖的語言即為：給定一個圖 G ，G 是否有哈密頓圈。
判斷條件
與歐拉圖的情形不同，到目前為止還未找到判斷一個圖是否是哈密頓圖的非平凡的充要條件。事實上這是圖論中尚未解決的主要問題之一。哈密頓圖有很多充分條件，例如，
（1）若圖的最小度不小於頂點數的一半，則圖是哈密頓圖；
（2）若圖中每一對不相鄰的頂點的度數之和不小於頂點數，則圖是哈密頓圖。
另外，還有很多用度序列、度和、圖的堅韌度等參數給出的充分條件。
哈密頓圖的充分條件和必要條件
定理1： 設無向圖G是哈密頓圖，V1是V的任意的非空子集， p(G-V1)≤|V1| 其中，p(G-V1)為從G中刪除V1(刪除V1中各頂點及關聯的邊)後所得到的圖的連通分支。
定理2： 設G是n(n≥3)階無向簡單圖，如果G中任何一對不相鄰的頂點度數之和都大於等於n，則G是哈密頓圖。
定理3： 在n(n≥2)階有向圖D=中，如果所有有向邊均用無向邊代替，所得無向圖中含生成子圖Kn，則有向圖中存在哈密頓圖。
推論： n(n≥3)階有向完全圖為哈密頓圖。
哈密頓路徑也稱作哈密頓鏈，指在一個圖中沿邊訪問每個頂點恰好一次的路徑。尋找這樣的一個路徑是一個典型的NP-完全(NP-complete）問題。後來人們也證明了，找一條哈密頓路的近似比為常數的近似算法也是NP完全的。
算法級別
一般地，尋找一個圖的哈密頓圈問題是 NP 困難的。因此通常都是用窮舉搜尋的方法來判定一個圖是否含有哈密頓路或圈。後來魯賓（F.Rubin）利用推演的方法給出了一個好一點的搜尋步驟來找出圖裡的一些或者全部的哈密頓路或圈，安格魯因（D.Angluin）和瓦利安特（L.G.Valiant）設計的機率算法對哈密頓路或圈的尋找也是非常有用的。尋找哈密頓路的確定算法雖然很難有多項式時間的，但是這並不意味著只能進行時間複雜度為
暴力搜尋。利用狀態壓縮動態規劃，我們可以將時間複雜度降低到
，具體算法是建立方程f[i][S][j]，表示經過了i個節點，節點都是集合S的，到達節點j時的最短路徑。每次我們都按照點j所連的節點進行轉移。
哈密頓圖及其判定方法可以解決中國郵路問題、旅行售貨員問題、排座位問題、判定圖是否可一筆畫問題。
