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