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