共找到2條詞條名為哈密頓圖的結果 展開
- 哈密頓圖
- 哈密頓圈
哈密頓圖
哈密頓圖
哈密頓通路（迴路）與哈密頓圖（Hamilton圖）通過圖G的每個結點一次，且僅一次的通路（迴路），就是哈密頓通路（迴路）。存在哈密頓迴路的圖就是哈密頓圖。
美國圖論數學家奧勒在1960年給出了一個圖是哈密爾頓圖的充分條件：對於頂點個數大於2的圖，如果圖中任意兩點度的和大於或等於頂點總數，那這個圖一定是哈密頓圖。閉合的哈密頓路徑稱作哈密頓圈，含有圖中所有頂點的路徑稱作哈密頓路徑。
圖的哈密頓圈是指包含圖的所有頂點的圈。類似地，包含圖的所有頂點的路稱為圖的哈密頓路（Hamilton path）。一個圖若包含哈密頓圈，則稱這個圖為哈密頓圖（Hamiltonian graph）。這種路和圈之所以用哈密頓的名字命名，是因為哈密頓在1856年發明了正 12 面體數學遊戲：從正 12 面體的一個頂點出發沿棱行走，能否經過每一個頂點恰好一次回到出發點。用圖的語言即為：給定一個圖G，G是否有哈密頓圈。
哈密頓圖
哈密頓圖的充分條件和必要條件
⑴在無向簡單圖G=中½V½³3,任意不同結點，則G是哈密頓圖（充分條件，定理4）。
⑵有向完全圖D=；，若，則圖D是哈密頓圖（充分條件，定理5推論）。
⑶設無向圖G=,"V1ÌV，則P(G－V1）£½V1½；（必要條件，定理3）
若此條件不滿足，即$V1ÌV，使得P(G－V!)>½V1½；，則G一定不是哈密頓圖（非哈密頓圖的充分條件）。
哈密頓路徑也稱作哈密頓鏈，指在一個圖中沿邊訪問每個頂點恰好一次的路徑。尋找這樣的一個路徑是一個典型的NP-完全(NP-complete）問題。後來人們也證明了，找一條哈密頓路的近似比為常數的近似演演算法也是NP完全的。
尋找哈密頓路的確定演演算法雖然很難有多項式時間的，但是這並不意味著只能進行時間複雜度為O(n!*n）暴力搜索。利用狀態壓縮動態規劃，我們可以將時間複雜度降低到O（2^n*n^3），具體演演算法是建立方程f[i][S][j]，表示經過了i個節點，節點都是集合S的，到達節點j時的最短路徑。每次人們都按照點j所連的節點進行轉移。
