【文章內容簡介】 。 一個圖假如含有哈密爾頓回路，則這個圖就是哈密爾頓圖 。 哈密爾頓圖的集中判定方法 那么當我們拿到一個圖的時候，怎么樣去判斷它是不是一個哈密爾頓圖呢？如果是一個頂點較少的圖，那么有時候我們可以通過簡單的嘗試和錯誤的方法來判定。但是當頂點較多、通路較復雜的情況下，這種方法就會讓我們感到焦頭爛額，同時準確率也會大大下降。于是很多數學家開始嘗試找到一種判定哈密爾頓的充分必要條件。遺憾的是至今為止還沒有一種判定的充分必要條件，事實上，想要找到一個完全充分適用的判定方法幾乎是沒有可能的。但是數學家們依然沒有放棄尋找一種簡單的判定哈密爾頓圖的方法，這就形成了圖論上一個著名的哈密爾頓問題。 雖然目前得到的判定方法大多是 存在一些充分不必要或者必要不充分的條件 ，但是對于平時問題的解決和簡單的應用來說，在很多時候還是能起到簡單判定的作用。下面 將解析幾種相對好的方法：由于 對 于 任意一個圖來說 ， 如果它是哈密爾頓圖，它的基礎簡單圖 一定 是哈密爾頓圖，所以 在判定的時候 我們只要考慮簡單圖 。 狄拉克定理 和奧勒定理 最早提出判定哈密爾頓圖的是 英國的數學家狄拉克。狄拉克定理需要做的是記錄每個頂點 X 上有多少條通路，記通過頂點 X 的通路個數為 D(X)，當圖的每個的頂點的 D(X)相當大時，這個圖就是哈密爾頓圖。 定理 1（ 狄拉克定理）： 對于 任意給定的一個圖，如果這個圖的頂點數 3n? ，而且 ( ) n/ 2DX? ， 那么這個圖就是哈密爾頓圖 。 狄拉克發(fā)現上述定理的八年后，經過不斷的嘗試和總結，著名的美國圖論學家奧斯坦奧勒繼續(xù)了狄拉克的工作，推廣了狄拉克定理，得到了一個判定哈密爾頓圖的基礎結論，為后面的研究打開了一個方向。 定理 2（奧勒定理） ： 對于任意給定的一個圖，如果這個圖的頂點數 3n? ， 對于任意的兩個頂點 x、 y有 ( ) ( )D x D y n??，那么這個圖一定是哈密爾頓圖。 博薩定理 和薩瓦達定 理 5 在奧勒定理被發(fā)現以后，一個叫博薩德的匈牙利少年 用一篇僅有一頁長的論文對奧勒定理 進行了推廣，得到了一個重要的定理，引起了數學界的廣泛關注。 為了能更好的理解博薩定理的結論，我們可以引入一些記號：對于 任意的一個圖 G， x1,x2,? ,xn 在這里分別表示圖 G的所有頂點，且序列數是由小到大排列的， 我們用 D(G)表示序列（ D(x1),D(x2),? ,D(xn)） ,即存在關系有 D(x1)≤D(x2) ≤ ? ≤ D(xn)。 再假設有兩個序列其具有相同個數的數字： X=（ x1， x2， ? ， xn）； Y=（ y1， y2， ? ， yn）。 我們用 X≥ Y表示當且僅當對于每一個 i= ? 、 n， j= ? 、 n，都滿足 xi≥ yj。 例如： X=（ 1， 2， 3， 4）； Y=（ 5， 6， 7， 8）； Z=（ 6， 4， 5， 3）。 我們可以得到 Y≥ X,但是 Z≥ X卻是錯誤的。 然后我們定義每一個 3n? 的的整數得到一個序列 P(n)： 當 n 是奇數時，我們可以將 P(n)定義成整數列： P(n)=（ 1,2,3,4， ? ， n52 ， n32 ， n12 ， n12 ， n+12 ， ? ， n+12 ），一共包含n個數。 當 n 是偶數時，我們可以將 P(n)定義成整數列： P(n)=（ 1,2,3,4， ? ， n 22? ， n12? ， n2 ， n2 ， ? ， n2 ） 一 共包含 n 個數 。 根據定義我們可以得到： P(3)= （ 1， 2， 2） ； P(4)= （ 1， 2， 2， 2）； P(5)= （ 1， 2， 2， 3， 3）； P(6)= （ 1， 2， 3， 3， 3， 3）； P(7)= （ 1， 2， 3， 3， 4， 4， 4）； P(8)= （ 1， 2， 3， 4， 4， 4， 4， 4）； 有了上面這些基礎說明，我們就能很清楚的闡述博薩德的重要發(fā)現了： 定理 3（ 博 薩定理），任意一個 3n? 的圖，它的 D(G)滿足關系式有 D(G)≥ P(n),那么圖 G就是哈密爾頓圖。 博薩定理解決了很大一部分的哈密爾頓圖的判定問題，但是依然還存在一定的問題，不滿足博薩定理的圖不一定不是哈密爾頓圖，很多人不斷思索如何改進，很多數學家提出了很多種改進方案，但是經過比較之后，捷克的數學家薩瓦達的結論脫穎而出。目前為止，薩瓦達定理依舊是一種較好的哈密爾頓圖的判定方法。他的結論如下。 定理 4（薩瓦達定理）任意一個 3n? 的圖 G，且 D(G)=（ a1,a2,? ,an）滿足鞋面的條件：對于每一個小于 n2 的整數 i 的兩個不等式 a1≥ i+1， an1≥ ni，至少 6 有一個是成立的，那么圖 G就一定是哈密爾頓圖。 補充的一個必要定理 薩瓦達定理對哈密爾頓圖的判定做出了很大的改進，讓我們又多了一種簡單的方法，但是依然存在哈密爾頓圖不滿足薩瓦達定理。這個時候我們需要用到一個哈密爾頓圖的必要條件。這個條件敘述如下： 定理 5（一個判定的必要條件） ：設一個無向 圖 G=(V,E)是一個哈密爾頓圖， V1是 V 的一個非空子集，則有 P(GV1)≤ |V1|。其中 P(GV1)表示從 G 中刪除 V1得到的連同分支數。 這個條件的必要性可以由一下方法證明： 證明 ：假設 C是圖 G中的一條哈密爾頓回路 。 若 V1 當中的頂點是在 C上彼此相鄰的頂點，那么顯然有： P(CV1)=1≤ |V1|； （ 2） 若 V1 中的頂點是在 C上存在 m個互不相鄰，那么 就有： P(CV1)=m≤ |V1| 所以無論 V1 中的頂點在 C 上是相鄰或是不相鄰，或者兼有，都可以得到結論 P(CV1)≤ |V1| 同時由于 C 是圖 G的生成子圖，所以可以得到： P(CV1)≤ P(GV1) ≤ |V1| 一般時候定理 5 可以用來判定一個圖是非哈密爾頓圖 。 判定哈密爾頓圖的方法還有很多，但是最為常用的就是上述的五種方法，當然，時至今日，不乏有比這五種方法更為準確全面的方法，但是在這里就不一一介紹了。 實例 解析 為了能夠讓讀者更好的了解前文介紹的幾種方法，下面舉幾個實例來進行驗證。 圖 21：圖 G G2 在上圖中的兩個圖 G G2 可以簡單的應用定理 1（狄拉克定理）得到， G1中的每個頂點 x 都有 D(x)=3，而 n=4，所以有 D(x)=3≥ 4/2=2。同樣圖 G2 中， 7 任何一個頂點都有 D(x)=4，而 n=6，所以有 D(x)=3≥ 6/2=3。由此可以判定圖 GG2是哈密爾頓圖。 這兩個圖的判定同樣可以應用奧勒定理 進行判定 ，在圖 G1 中任意兩點 x、 y，有 D(x)+D(y)=6≥ 4；在圖 G2 中任意兩點 x、 y，有 D(x)+D(y)=8≥ 6，同樣可以判定圖 G G2 是哈密爾頓圖。 圖 22：圖 G G4 為了更好的體現 博薩定理和薩瓦達定理的優(yōu)越性，可以使用圖 G3 來進行比較。應用 狄拉克定理時， 明顯 n=5 且 D(x)=2≤ 5/2=n/2，不能判 定它是哈密爾頓圖。同樣 使用奧勒定理時 min（ D(x)+D(y)） =4≤ 5/2=n/2，也不能判定。但是簡單的觀察就可以發(fā)現圖 G3 是一個哈密爾頓圖。這個時候我們就可以