哈密爾頓圖的判定及應用論文

時間：2021-03-18 10:04:30 論文我要投稿

哈密爾頓圖的判定及應用論文

　　引導語：哈密爾頓圖的研究是圖論中不可或缺的一部分，這個問題的研究已經應用到了各個領域。合理的利用哈密爾頓圖的結論，不僅可以節約大量的時間，更可以降低發展的成本。因此很多學者致力于哈密爾頓圖的問題研究，也得到了很多了不起的突破。

哈密爾頓圖的判定及應用論文

　　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 結論

　　哈密爾頓圖相可以應用的范圍已經越來越廣闊，從工業鋪路到農業灌溉，航空路線到海底勘探，從國家的發展到公司的運輸，都可以用到哈密爾頓圖的知識。哈密爾頓圖的研究已經顯得越來越重要，在效率第一的當今社會，恰當的應用哈密爾頓圖的研究結果可以可以大大提高工作的效率和節約發展成本，為可持續發展提供不可或缺的支持。本文借鑒總結了大量前人的結論，著重介紹了哈密爾頓圖判定上的五種方法和結論，并初步對這五種方法的應用范圍進行了分類。在哈密爾頓圖的應用方面，著重介紹了貨郎擔問題的研究。在解決方法上又介紹了樹的搜索法，同時也說明了解決方法的未來發展方向。

【哈密爾頓圖的判定及應用論文】相關文章：

波動圖象與振動圖象的綜合應用練習題05-29

學年判定總結03-13