哈密爾頓圖的判定及應用論文
哈密爾頓圖的判定及應用論文
引導語：哈密爾頓圖的研究是圖論中不可或缺的一部分，這個問題的研究已經應用到了各個領域。合理的利用哈密爾頓圖的結論，不僅可以節約大量的時間，更可以降低發展的成本。因此很多學者致力於哈密爾頓圖的問題研究，也得到了很多了不起的突破。
1 引言
在查閱了大量資料後，可以發現哈密爾頓圖在數學理論研究和現實應用中都具有重要的地位。哈密爾頓圖的研究解決了大量的問題，但是還是有很多的問題還未得到解決。其中較為著名的就是關於貨郎擔問題的解決方案，至今還沒有很好的答案。本文在綜合了各種哈密爾頓圖的判定方法之後，嘗試用多種方法去解決貨郎擔問題，在比較後，找到一種相對較好的方法，也為將來的繼續研究提供研究方向。
1.1 哈密爾頓圖的起源
哈密爾頓(Hamilton)是一位出生在愛爾蘭的天文學家和數學家. 他的一生是很豐富多彩的，自從他發現“四元數”後，他又發現了另一種稱之為“The Icosian Calculus”的代數系統，這個系統包含有乘法和加法的運算運算元，但是乘法並不滿換律(即xy-yx這個規律)。
他發現的這個代數系統是和正則12 面體有關的。於是在1859 年他提出下列周遊世界的遊戲:
在正十二面體的二十個頂點上依次標記倫敦、巴黎、莫斯科、華盛頓、北京、東京等世界著名大城市; 正十二面體的稜( 邊) 表示連線這些城市的路線。問: 能否在圖中做一次旅行,從頂點到頂點, 沿著邊行走, 經過每個城市恰好一次之後再回到出發點?曾經有很多人不斷追尋這個遊戲的答案。可以應用拓撲的思想，將這正十二面體“拉平”將會得到一個和它同構的平面圖(如圖1-1)，這樣進行就可以將這個遊戲轉化為：要求必須沿著正十二面體的稜，怎樣才能走完正則十二面體上的所有頂點，而且最後又回到起點的問題。
圖1-1：哈密爾頓周遊世界圖
從此人們將這類圖稱作哈密爾頓圖，哈密爾頓圖的研究也開始慢慢建立起來。
1.2 研究背景和意義
哈密爾頓圖是圖論的重要的一部分，隨著數學和科學技術的蓬勃發展，它的應用已經滲透到自然科學、社會科學的各個領域。然而其發展的時間並不長，所以還有很多的地方有待改進。
其在貨郎擔問題的研究上，更是進幾十年才受到重視，然而他的應用卻是非常廣泛的，同樣的方法，可以用以地震搜救，糧食分派，糧食運輸，外出旅遊等類似的各個方面。不僅能降低資源浪費，還可以最大化成果，對於受困的群眾，多一分鐘就可以多一分生存的希望。
研究哈密爾頓圖的判定不僅僅在數學和科學領域具有很高的的研究價值，在現實應用中更是可以得到有價值的結果。因此，本文的研究方向是很具有現實意義。
1.3 哈密爾頓圖判定方法的發展
1952年英國數學家狄拉克最早提出了判定哈密爾頓圖的充分條件， n 階連通圖G, 若δ≥n/ 2, 則G 是哈密爾頓圖。為哈密爾頓圖的發展奠定了基礎。
8年後即1960年美國著名的圖論專家奧斯坦·奧勒推廣狄拉克的工作，得到了更為廣泛的結果--奧勒定理。：對於頂點個數大於2的圖，如果圖中任意兩點度的和大於或等於頂點總數，那這個圖一定是哈密爾頓圖。
1962年，匈牙利的一個叫博薩的少年發表了僅有一頁長的論文，雖然論文很短，只有僅僅一頁，但其結果卻推廣了奧勒定理。有一個n≥3的圖G，它的D(G)滿足不等式D(G)≥P(n)，那麼圖G就是哈密爾頓圖。
這一結果無疑是非常具有價值的，所以在當時引起了很多的關注.在之後的幾年中，很多人都嘗試改進他的工作，使其有一個系統清晰的結果，最後終於有一個捷克的青年數學家薩瓦達得到了比他更為完整的結論。有一個n≥3的圖G，而且D(G)=(a1,a2,...an)滿足條件對於任何一個小於n/2的正整數i的不等式a1≥i+1，an-1≥n-i最少有一個是成立的那麼圖G就是哈密爾頓圖。
1995 年趙俊和宋序平只研究了3 連通圖( 還遺留2 連通的情況) 的鄰域並條件N C+ δ≥n 的哈密爾頓連通圖, 得到:
3 連通n 階圖G, 若N C+ δ≥n, 則是哈密爾頓連通圖或例外圖。
2001年2月廣西大學計算機與資訊工程學院的羅示豐提出了一種判別哈密第2 步: 找出圖G = ( V, E) 度數最大的頂點X k; 第3 步: 刪去X k 以及與
X k 關聯的所有邊; 第4 步: V←V-{X k} , E←E-{邊與X k關聯的邊} ,
第2 步。這種方法為計算機的判別提供了一個清晰的方向。
時至今日，無論國內還是國外都已經發現了哈密爾頓圖的'巨大作用，很多研究者也把目光放在了哈密爾頓圖的判定問題的解決上，相信不久的將來，就會有更加重大的突破。
1.4 本文的研究方向
從哈密爾頓圖的問題出現以來，無數的學者進行了多方面的研究，也發現了無數哈密爾頓圖的性質，從而對其進行判定。然而問題的複雜性讓我們的研究時間還是顯得非常的短暫，哈密爾頓圖的判定問題至今也沒有一個確定的最好的方法。而根據哈密爾頓圖的判定條件的不同，選用的方法也不盡相同。
本文主要介紹哈密爾頓圖判定的狄拉克定理、奧勒定理、博薩定理、薩瓦達定理。對這些定理進行詳細的介紹及例項演示。在這些演示的基礎上，再補充定理，以完善這些定理中的缺陷。最後將這些方法應用到著名的貨郎擔問題上來進行應用。在本文中其他定理及應用由於篇幅原因就不一一贅述了。
2 哈密爾頓圖的判定
2.1 哈密爾頓圖的定義
設G 是一個圖，包含圖G中的每個頂點的路就稱為哈密爾頓路。透過圖G 中每個頂點有且僅有一次的通路就稱為哈密爾頓通路。透過圖G中的每個頂點有且僅有一次的迴路就稱為哈密爾頓迴路。一個圖假如含有哈密爾頓迴路，則這個圖就是哈密爾頓圖。
2.2 哈密爾頓圖的集中判定方法
那麼當我們拿到一個圖的時候，怎麼樣去判斷它是不是一個哈密爾頓圖呢?如果是一個頂點較少的圖，那麼有時候我們可以透過簡單的嘗試和錯誤的方法來判定。但是當頂點較多、通路較複雜的情況下，這種方法就會讓我們感到焦頭爛額，同時準確率也會大大下降。於是很多數學家開始嘗試找到一種判定哈密爾頓的充分必要條件。遺憾的是至今為止還沒有一種判定的充分必要條件，事實上，想要找到一個完全充分適用的判定方法幾乎是沒有可能的。但是數學家們依然沒有放棄尋找一種簡單的判定哈密爾頓圖的方法，這就形成了圖論上一個著名的哈密爾頓問題。
雖然目前得到的判定方法大多是存在一些充分不必要或者必要不充分的條件，但是對於平時問題的解決和簡單的應用來說，在很多時候還是能起到簡單判定的作用。下面將解析幾種相對好的方法：由於對於任意一個圖來說，如果它是哈密爾頓圖，它的基礎簡單圖一定是哈密爾頓圖，所以在判定的時候我們只要考慮簡單圖。
2.2.1 狄拉克定理和奧勒定理
最早提出判定哈密爾頓圖的是英國的數學家狄拉克。狄拉克定理需要做的是記錄每個頂點X上有多少條通路，記透過頂點X的通路個數為D(X)，當圖的每個的頂點的D(X)相當大時，這個圖就是哈密爾頓圖。
定理1(狄拉克定理)：對於任意給定的一個圖，如果這個圖的頂點數n≥3，而且D(X)≥n/ 2，那麼這個圖就是哈密爾頓圖。
狄拉克發現上述定理的八年後，經過不斷的嘗試和總結，著名的美國圖論學家奧斯坦·奧勒繼續了狄拉克的工作，推廣了狄拉克定理，得到了一個判定哈密爾頓圖的基礎結論，為後面的研究打開了一個方向。
定理2(奧勒定理)：對於任意給定的一個圖，如果這個圖的頂點數n≥3，對於任意的兩個頂點x、y有D(x)+D(y)≥n，那麼這個圖一定是哈密爾頓圖。
2.2.2 博薩定理和薩瓦達定理
在奧勒定理被發現以後，一個叫博薩的匈牙利少年用一篇僅有一頁長的論文對奧勒定理進行了推廣，得到了一個重要的定理，引起了數學界的廣泛關注。
為了能更好的理解博薩定理的結論，我們可以引入一些記號：對於任意的一個圖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=1、2、、n，j=1、2、、n，都滿足xi≥yj。
例如：X=(1，2，3，4);
Y=(5，6，7，8);
Z=(6，4，5，3)。
我們可以得到Y≥X,但是Z≥X卻是錯誤的。
然後我們定義每一個n≥3的的整數得到一個序列P(n)：
當n是奇數時，我們可以將P(n)定義成整數列：
n-5n-3n-1n-1n+1n+1P(n)=(1,2,3,4，，，，，，，，)，一共包含222222n個數。
當n是偶數時，我們可以將P(n)定義成整數列：
nnnnnP(n)=(1,2,3,4，，-2，-1，，，，)一共包含n個數。 22222
根據定義我們可以得到：
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);
有了上面這些基礎說明，我們就能很清楚的闡述博薩的重要發現了：
定理3(博薩定理)，任意一個n≥3的圖，它的D(G)滿足關係式有D(G)≥P(n),那麼圖G就是哈密爾頓圖。
博薩定理解決了很大一部分的哈密爾頓圖的判定問題，但是依然還存在一定的問題，不滿足博薩定理的圖不一定不是哈密爾頓圖，很多人不斷思索如何改進，很多數學家提出了很多種改進方案，但是經過比較之後，捷克的數學家薩瓦達的結論脫穎而出。目前為止，薩瓦達定理依舊是一種較好的哈密爾頓圖的判定方法。他的結論如下。
定理4(薩瓦達定理)任意一個n≥3的圖G，且D(G)=(a1,a2,,an)滿足鞋面n的條件：對於每一個小於的整數i的兩個不等式a1≥i+1，an-1≥n-i，至少2
有一個是成立的，那麼圖G就一定是哈密爾頓圖。
2.2.3補充的一個必要定理
薩瓦達定理對哈密爾頓圖的判定做出了很大的改進，讓我們又多了一種簡單的方法，但是依然存在哈密爾頓圖不滿足薩瓦達定理。這個時候我們需要用到一個哈密爾頓圖的必要條件。這個條件敘述如下：
定理5(一個判定的必要條件)：設一個無向圖G=(V,E)是一個哈密爾頓圖，V1是V的一個非空子集，則有P(G-V1)≤|V1|。其中P(G-V1)表示從G中刪除V1得到的連同分支數。
這個條件的必要性可以由一下方法證明：
證明：假設C是圖G中的一條哈密爾頓迴路。
若V1當中的頂點是在C上彼此相鄰的頂點，那麼顯然有：
P(C-V1)=1≤|V1|;
(2) 若V1中的頂點是在C上存在m個互不相鄰，那麼就有：
P(C-V1)=m≤|V1|
所以無論V1中的頂點在C上是相鄰或是不相鄰，或者兼有，都可以得到結論
P(C-V1)≤|V1|
同時由於C是圖G的生成子圖，所以可以得到：
P(C-V1)≤P(G-V1) ≤|V1|
一般時候定理5可以用來判定一個圖是非哈密爾頓圖。
判定哈密爾頓圖的方法還有很多，但是最為常用的就是上述的五種方法，當然，時至今日，不乏有比這五種方法更為準確全面的方法，但是在這裡就不一一介紹了。
2.3 例項解析
為了能夠讓讀者更好的瞭解前文介紹的幾種方法，下面舉幾個例項來進行驗證。
圖2-1：圖G1、G2
在上圖中的兩個圖G1、G2可以簡單的應用定理1(狄拉克定理)得到，G1中的每個頂點x都有D(x)=3，而n=4，所以有D(x)=3≥4/2=2。同樣圖G2中，
任何一個頂點都有D(x)=4，而n=6，所以有D(x)=3≥6/2=3。由此可以判定圖G1、G2是哈密爾頓圖。
這兩個圖的判定同樣可以應用奧勒定理進行判定，在圖G1中任意兩點x、y，有D(x)+D(y)=6≥4;在圖G2中任意兩點x、y，有D(x)+D(y)=8≥6，同樣可以判定圖G1、G2是哈密爾頓圖。
圖2-2：圖G3、G4
為了更好的體現博薩定理和薩瓦達定理的優越性，可以使用圖G3來進行比較。應用狄拉克定理時，明顯n=5且D(x)=2≤5/2=n/2，不能判定它是哈密爾頓圖。同樣使用奧勒定理時min(D(x)+D(y))=4≤5/2=n/2，也不能判定。但是簡單的觀察就可以發現圖G3是一個哈密爾頓圖。這個時候我們就可以用博薩定理進行判定。
根據博薩定理有D(G3)=(2，2，3，3，4)，而P(5)=(1，2，2，3，3)，根據比較就有D(G3)≥P(5)，從而可以得到圖G3是哈密爾頓圖。
同樣也可以根據薩瓦達定理來進行判定，因為n=5，所以小於n/2的i有i=1、2。
當i=1時，a1=2≥2=i+1，成立;
當i=2時，an-1=3≥3=n-i，成立;
同樣可以判定圖G3是哈密爾頓圖。
然而博薩定理和薩瓦達定理同樣是不完善的，這一點圖G4給我們作出了很好的例子。在應用博薩定理時D(G4)=(3，3，3，3，3，3，3，3)，P(8)= (1，2，3，4，4，4，4，4);此時我們是不能說D(G4)≥P(8)的，沒辦法判定G4是哈密爾頓圖。
薩瓦達定理也對這個問題表示無能為力，在圖G4中n=8，所以小於n/2的正整數i=1、2、3。當i=3時，a1=3≥4=i+1，不成立;an-1=3≥5=n-i，不成立，此時違反薩瓦達定理，所以也不能判定G4是哈密爾頓圖。
然而簡單觀察後就可以發現圖G4是一個哈密爾頓圖，所以博薩定理和薩瓦達定理是有一定的缺陷的。
圖G4為我們的進一步研究提供了方向，讓我們能夠不斷的深入。相信在不久的將來會有一種簡單的方法可以幫助我們得出結論。
3 哈密爾頓圖的判定在貨郎擔問題中的應用
3.1貨郎擔問題的由來和在現實中的應用
貨郎擔問題是由德國的著名數學家肯·蒙那哥在1932年提出來的，80年來一直是哈密爾頓圖的應用中的最典型的例子，無數人對其進行廢寢忘食的研究。這個問題可以表述為：假設一個售貨員需要在n個城市之間進行銷售，現在我們已經知道了這n個城市中任意的兩個城市之間的距離，現在售貨員需要選擇一條路線使得從出發的城市開始，經過其他的城市有且僅有一次，最後回到出發點，問這個售貨員應該怎麼樣選擇路線呢。
將上述的問題進行數學提煉後所求的問題可以轉化為，在一個加附了權值的完全圖中，尋找一個權值最小的哈密爾頓迴路。看似簡單，但實際上卻是非常複雜的問題，至今任何一種簡化的解決方法都能夠帶來無法想象的價值。因為生活中需要遇到貨郎擔問題的地方實在是太多了，例如：
(1)當我們外出旅遊的時候，提前安排好路程最短的路線，不僅可以節省交通上的成本，還可以得到更多的時間來參觀。
(2)當地震等天災發生時，我們需要組建搜救隊伍對受災區域進行救援，在受災程度相近的情況下，安排合適的搜救路線，不僅可以挽回很多的經濟損失，更重要的是可以挽救更多的生命。
(3)再假設當我們出差坐飛機時，由於各地的情況不同導致各個地方之間的價格會不一樣。我們選擇合適的城市順序，可以讓我們得到大幅度的節約成本。為公司創造更多的利潤。
這類的問題還有很多，而這些問題都可以歸結為貨郎擔問題。所以貨郎擔問題的研究是與生活直接相關的，是非常具有現實意義的。
3.2貨郎擔問題解決方法
那麼到底應該怎樣去解決貨郎擔問題呢，遺憾的是直到目前為止，雖然無數人為止奮鬥，也得到了一些正確的結論，但是還是沒有一種能夠簡單的解決哈密爾頓圖的方法。美國的《管理科學》中有一篇討論“貨郎擔問題”的文章，該文中提到：人類由於他的計算能力的限制，在解決貨郎擔問題上並不好。所以，現在人們對於這個問題的研究已經開始藉助電子計算機來進行實現。1979年11月7日《紐約時報》上出現了一篇很有影響力的文章，它的標題為《蘇聯的發現震動數學界》，這篇文章雖然有一定的誇大成分存在，但是他所說的把貨郎擔問題的解決和計算機聯絡起來的思想確實沒有錯的。2001年廣西大學計算機與資訊工程學院的羅示豐提出了用計算機判定哈密爾頓圖的方法。雖然這個方法還未應用到貨郎擔問題的解決上，但是卻也堅定了很多人繼續往這個方向研究的信心，在不久的將來這個問題一定可以獲得更大的突破。
德國是一個非常嚴謹的國家，德國的波恩大學的一位數學家很好的發揮了這一特點，當他知道西德有120個有鐵路穿過的城市後，就準備找到一個最短路程的迴路，應該怎麼樣去跑。他費盡心血從鐵路局找到了準確的城市間鐵路的長度，把整個問題變成了一個有7140個變數，120個方程及96個不等式的線性規劃問
題，人類的大腦已經對這樣的問題表示無能為力了，最後不得不用電子計算機去算，才得到了最短的迴路是6942公里。結果見圖3-1。
圖3-1：西德120個城市最短路線圖
3.3樹的搜尋法
那麼在一般情況下我們可以借用什麼方法來解決貨郎擔問題呢?在這裡介紹一種較為簡單的方法--------樹的搜尋法。
為了更好的理解這個方法，在這裡我們舉一個例子加以說明：設共有A、B、
C、D、E五個城市，我們需要從A出發經過B、C、D、E四個城市有且僅有一次，最後再回到A。A、B、C、D、E五座城市之間的距離由下表進行表出：
圖3-2：五個城市之間的連通情況
我們選擇從點A出發，先寫A(0)，0表示最初沒有出發路線是的路程長度是0，然後我們可以列出下一步可能到達的城市，分別由B、C、D、E，可以得到四個節點為AB(10)、AC(20)、AD(50)、AE(70)。見圖3-3。
圖3-3：樹的搜尋法第一步
現在我們可以看到由城市B可能到達的城市有C、D、E，把節點AB(10)劃掉，我們可以得到三個新的節點ABC(10+20)、ABD(10+50)、ABE(10+60)後面的20、50、60分別表示BC、BD、BE的長度，以此類推我們還可以得到的新節點有ACB(40)、ACD(70)、ACE(100)、ADB(100)、ADC(100)、ADE(80)、AEB(130)、AEC(150)、AED(100)九個節點。見圖3-4。
圖3-4：樹的搜尋法第二步
根據上述法則繼續推廣，就可以知道，假設是ABC的路徑，那麼到達C城以後，就只剩下了兩種可能路徑：ABCDEA和ABCEDA，於是我們劃掉節點ABC(30)，得到兩個新的節點ABCDEA(180)和ABCEDA(190)。以此類推，我們可以得到其他的二十二個節點ABDCEA(260)、ABDECA(190)、ABECDA(250)、ABEDCA(170)、ACBDEA(190)、ACBEDA(180)、ACDBEA(250)、ACDEBA(170)、ACEBDA(260)、ACEDBA(190)、ADBCEA(270)、ADBECA(260)、ADCBEA(250)、ADCEBA(250)、ADEBCA(180)、ADECBA(190)、AEBCDA(250)、AEBDCA(250)、AECBDA(270)、AECDBA(260)、AEDBCA(190)、AEDCBA(180)。見圖3-5。
圖3-5：樹的搜尋法第三步
根據圖我們可以發現，在5個城市之間我們一共可以得到二十四條迴路，其中最短的兩條為ABEDCA(170)和ACDEBA(170)。由此我們得到了在五個城市之間銷售的最佳路線。
做完這全部的工作後，我們回過頭去看這個方法，可以發現在最後一步的計算時，一部分的工作是可以省略的。比如當我們找到第一條迴路ABCDEA時，我們可以知道這條路徑的長度是180，那麼在之後的計算中，一旦發現路徑的長度明顯大於180，或者上一層的節點的數值已經大於180了，那麼我們直接可以用“≥180”來代替具體的數值。當計算到ABEDCA這條路徑時，我們發現數值是170，那麼之後的數值如明顯大於170，那麼久可以用“≥170”來替代，這樣可以節省一定的計算時間，加快得出結果的速度。
在上面方法展示的過程中我們可以發現，這樣的搜尋方法在地點數量較少的時候還比較試用，一旦地點數量達到十個，那麼我們的計算量將變的嚇人，甚至可以說是超過了人腦的計算能力，我們會感到十分的繁瑣。如果十個地點還可以
勉強算出來，那麼地點數量達到300個或者500個呢?那時候的計算量是我們無法想象的，而這種情況對於像中國這樣的大國來說，是非常現實的問題。這個時候我們就不得不借助計算機的力量。
計算機到底可以提升多少的計算速度呢?一個例子能夠很好的說明問題：在美國工作的華籍數學家Lin Shen及Hong Saman等人在1977年的時候用電子計算器計算得到了一個有關於318個城市的貨郎擔問題。這個問題一旦化成線性規劃問題，那麼就要處理有50403個變數的方程式及不等式，人腦對於這樣的問題雖然不能說完全不能解決，但是所需要的時間將是難以想象的。而當時的Lin Shen等人藉助了一臺IBM的370—168式的電子計算機後，僅用了28.38分鐘就得到了一個最優解，納悶對於電子技術日新月異的今天，我們可能需要的時間已經不足一分鐘。兩者互相對比，讓我們不得不承認，以後的發展方向將更多的藉助計算機技術。
4 結論
哈密爾頓圖相可以應用的範圍已經越來越廣闊，從工業鋪路到農業灌溉，航空路線到海底勘探，從國家的發展到公司的運輸，都可以用到哈密爾頓圖的知識。哈密爾頓圖的研究已經顯得越來越重要，在效率第一的當今社會，恰當的應用哈密爾頓圖的研究結果可以可以大大提高工作的效率和節約發展成本，為可持續發展提供不可或缺的支援。本文借鑑總結了大量前人的結論，著重介紹了哈密爾頓圖判定上的五種方法和結論，並初步對這五種方法的應用範圍進行了分類。在哈密爾頓圖的應用方面，著重介紹了貨郎擔問題的研究。在解決方法上又介紹了樹的搜尋法，同時也說明了解決方法的未來發展方向。