哈密爾頓圖的判定及應(yīng)用論文

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

　　1 引言

　　在查閱了大量資料后，可以發(fā)現(xiàn)哈密爾頓圖在數(shù)學(xué)理論研究和現(xiàn)實應(yīng)用中都具有重要的地位。哈密爾頓圖的研究解決了大量的問題，但是還是有很多的問題還未得到解決。其中較為著名的就是關(guān)于貨郎擔(dān)問題的解決方案，至今還沒有很好的答案。本文在綜合了各種哈密爾頓圖的判定方法之后，嘗試用多種方法去解決貨郎擔(dān)問題，在比較后，找到一種相對較好的方法，也為將來的繼續(xù)研究提供研究方向。

　　1.1 哈密爾頓圖的起源

　　哈密爾頓(Hamilton)是一位出生在愛爾蘭的天文學(xué)家和數(shù)學(xué)家. 他的一生是很豐富多彩的，自從他發(fā)現(xiàn)“四元數(shù)”后，他又發(fā)現(xiàn)了另一種稱之為“The Icosian Calculus”的代數(shù)系統(tǒng)，這個系統(tǒng)包含有乘法和加法的運算算子，但是乘法并不滿換律(即xy-yx這個規(guī)律)。

　　他發(fā)現(xiàn)的這個代數(shù)系統(tǒng)是和正則12 面體有關(guān)的。于是在1859 年他提出下列周游世界的游戲:

　　在正十二面體的二十個頂點上依次標記倫敦、巴黎、莫斯科、華盛頓、北京、東京等世界著名大城市; 正十二面體的棱( 邊) 表示連接這些城市的路線。問: 能否在圖中做一次旅行,從頂點到頂點, 沿著邊行走, 經(jīng)過每個城市恰好一次之后再回到出發(fā)點?曾經(jīng)有很多人不斷追尋這個游戲的答案。可以應(yīng)用拓撲的思想，將這正十二面體“拉平”將會得到一個和它同構(gòu)的平面圖(如圖1-1)，這樣進行就可以將這個游戲轉(zhuǎn)化為：要求必須沿著正十二面體的棱，怎樣才能走完正則十二面體上的所有頂點，而且最后又回到起點的問題。

　　圖1-1：哈密爾頓周游世界圖

　　從此人們將這類圖稱作哈密爾頓圖，哈密爾頓圖的研究也開始慢慢建立起來。

　　1.2 研究背景和意義

　　哈密爾頓圖是圖論的重要的一部分，隨著數(shù)學(xué)和科學(xué)技術(shù)的蓬勃發(fā)展，它的應(yīng)用已經(jīng)滲透到自然科學(xué)、社會科學(xué)的各個領(lǐng)域。然而其發(fā)展的時間并不長，所以還有很多的地方有待改進。

　　其在貨郎擔(dān)問題的研究上，更是進幾十年才受到重視，然而他的應(yīng)用卻是非常廣泛的，同樣的方法，可以用以地震搜救，糧食分派，糧食運輸，外出旅游等類似的各個方面。不僅能降低資源浪費，還可以最大化成果，對于受困的群眾，多一分鐘就可以多一分生存的希望。

　　研究哈密爾頓圖的判定不僅僅在數(shù)學(xué)和科學(xué)領(lǐng)域具有很高的的研究價值，在現(xiàn)實應(yīng)用中更是可以得到有價值的結(jié)果。因此，本文的研究方向是很具有現(xiàn)實意義。

　　1.3 哈密爾頓圖判定方法的發(fā)展

　　1952年英國數(shù)學(xué)家狄拉克最早提出了判定哈密爾頓圖的充分條件， n 階連通圖G, 若δ≥n/ 2, 則G 是哈密爾頓圖。為哈密爾頓圖的發(fā)展奠定了基礎(chǔ)。

　　8年后即1960年美國著名的圖論專家奧斯坦·奧勒推廣狄拉克的工作，得到了更為廣泛的結(jié)果--奧勒定理。：對于頂點個數(shù)大于2的圖，如果圖中任意兩點度的和大于或等于頂點總數(shù)，那這個圖一定是哈密爾頓圖。

　　1962年，匈牙利的一個叫博薩的少年發(fā)表了僅有一頁長的論文，雖然論文很短，只有僅僅一頁，但其結(jié)果卻推廣了奧勒定理。有一個n≥3的圖G，它的D(G)滿足不等式D(G)≥P(n)，那么圖G就是哈密爾頓圖。

　　這一結(jié)果無疑是非常具有價值的，所以在當(dāng)時引起了很多的關(guān)注.在之后的幾年中，很多人都嘗試改進他的工作，使其有一個系統(tǒng)清晰的結(jié)果，最后終于有一個捷克的青年數(shù)學(xué)家薩瓦達得到了比他更為完整的結(jié)論。有一個n≥3的圖G，而且D(G)=(a1,a2,...an)滿足條件對于任何一個小于n/2的正整數(shù)i的不等式a1≥i+1，an-1≥n-i最少有一個是成立的那么圖G就是哈密爾頓圖。

　　1995 年趙俊和宋序平只研究了3 連通圖( 還遺留2 連通的情況) 的鄰域并條件N C+ δ≥n 的哈密爾頓連通圖, 得到:

　　3 連通n 階圖G, 若N C+ δ≥n, 則是哈密爾頓連通圖或例外圖。

　　2001年2月廣西大學(xué)計算機與信息工程學(xué)院的羅示豐提出了一種判別哈密第2 步: 找出圖G = ( V, E) 度數(shù)最大的頂點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 步。這種方法為計算機的判別提供了一個清晰的方向。

　　時至今日，無論國內(nèi)還是國外都已經(jīng)發(fā)現(xiàn)了哈密爾頓圖的'巨大作用，很多研究者也把目光放在了哈密爾頓圖的判定問題的解決上，相信不久的將來，就會有更加重大的突破。

　　1.4 本文的研究方向

　　從哈密爾頓圖的問題出現(xiàn)以來，無數(shù)的學(xué)者進行了多方面的研究，也發(fā)現(xiàn)了無數(shù)哈密爾頓圖的性質(zhì)，從而對其進行判定。然而問題的復(fù)雜性讓我們的研究時間還是顯得非常的短暫，哈密爾頓圖的判定問題至今也沒有一個確定的最好的方法。而根據(jù)哈密爾頓圖的判定條件的不同，選用的方法也不盡相同。

　　本文主要介紹哈密爾頓圖判定的狄拉克定理、奧勒定理、博薩定理、薩瓦達定理。對這些定理進行詳細的介紹及實例演示。在這些演示的基礎(chǔ)上，再補充定理，以完善這些定理中的缺陷。最后將這些方法應(yīng)用到著名的貨郎擔(dān)問題上來進行應(yīng)用。在本文中其他定理及應(yīng)用由于篇幅原因就不一一贅述了。

　　2 哈密爾頓圖的判定

　　2.1 哈密爾頓圖的定義

　　設(shè)G 是一個圖，包含圖G中的每個頂點的路就稱為哈密爾頓路。通過圖G 中每個頂點有且僅有一次的通路就稱為哈密爾頓通路。通過圖G中的每個頂點有且僅有一次的回路就稱為哈密爾頓回路。一個圖假如含有哈密爾頓回路，則這個圖就是哈密爾頓圖。

　　2.2 哈密爾頓圖的集中判定方法

　　那么當(dāng)我們拿到一個圖的時候，怎么樣去判斷它是不是一個哈密爾頓圖呢?如果是一個頂點較少的圖，那么有時候我們可以通過簡單的嘗試和錯誤的方法來判定。但是當(dāng)頂點較多、通路較復(fù)雜的情況下，這種方法就會讓我們感到焦頭爛額，同時準確率也會大大下降。于是很多數(shù)學(xué)家開始嘗試找到一種判定哈密爾頓的充分必要條件。遺憾的是至今為止還沒有一種判定的充分必要條件，事實上，想要找到一個完全充分適用的判定方法幾乎是沒有可能的。但是數(shù)學(xué)家們依然沒有放棄尋找一種簡單的判定哈密爾頓圖的方法，這就形成了圖論上一個著名的哈密爾頓問題。

　　雖然目前得到的判定方法大多是存在一些充分不必要或者必要不充分的條件，但是對于平時問題的解決和簡單的應(yīng)用來說，在很多時候還是能起到簡單判定的作用。下面將解析幾種相對好的方法：由于對于任意一個圖來說，如果它是哈密爾頓圖，它的基礎(chǔ)簡單圖一定是哈密爾頓圖，所以在判定的時候我們只要考慮簡單圖。

　　2.2.1 狄拉克定理和奧勒定理

　　最早提出判定哈密爾頓圖的是英國的數(shù)學(xué)家狄拉克。狄拉克定理需要做的是記錄每個頂點X上有多少條通路，記通過頂點X的通路個數(shù)為D(X)，當(dāng)圖的每個的頂點的D(X)相當(dāng)大時，這個圖就是哈密爾頓圖。

　　定理1(狄拉克定理)：對于任意給定的一個圖，如果這個圖的頂點數(shù)n≥3，而且D(X)≥n/ 2，那么這個圖就是哈密爾頓圖。

　　狄拉克發(fā)現(xiàn)上述定理的八年后，經(jīng)過不斷的嘗試和總結(jié)，著名的美國圖論學(xué)家奧斯坦·奧勒繼續(xù)了狄拉克的工作，推廣了狄拉克定理，得到了一個判定哈密爾頓圖的基礎(chǔ)結(jié)論，為后面的研究打開了一個方向。

　　定理2(奧勒定理)：對于任意給定的一個圖，如果這個圖的頂點數(shù)n≥3，對于任意的兩個頂點x、y有D(x)+D(y)≥n，那么這個圖一定是哈密爾頓圖。

　　2.2.2 博薩定理和薩瓦達定理

　　在奧勒定理被發(fā)現(xiàn)以后，一個叫博薩的匈牙利少年用一篇僅有一頁長的論文對奧勒定理進行了推廣，得到了一個重要的定理，引起了數(shù)學(xué)界的廣泛關(guān)注。

　　為了能更好的理解博薩定理的結(jié)論，我們可以引入一些記號：對于任意的一個圖G，x1,x2,,xn 在這里分別表示圖G的所有頂點，且序列數(shù)是由小到大排列的，我們用D(G)表示序列(D(x1),D(x2),,D(xn)),即存在關(guān)系有D(x1)≤D(x2) ≤≤D(xn)。再假設(shè)有兩個序列其具有相同個數(shù)的數(shù)字：

　　X=(x1，x2，，xn);

　　Y=(y1，y2，，yn)。

　　我們用X≥Y表示當(dāng)且僅當(dāng)對于每一個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卻是錯誤的。

　　然后我們定義每一個n≥3的的整數(shù)得到一個序列P(n)：

　　當(dāng)n是奇數(shù)時，我們可以將P(n)定義成整數(shù)列：

　　n-5n-3n-1n-1n+1n+1P(n)=(1,2,3,4，，，，，，，，)，一共包含222222n個數(shù)。

　　當(dāng)n是偶數(shù)時，我們可以將P(n)定義成整數(shù)列：

　　nnnnnP(n)=(1,2,3,4，，-2，-1，，，，)一共包含n個數(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(博薩定理)，任意一個n≥3的圖，它的D(G)滿足關(guān)系式有D(G)≥P(n),那么圖G就是哈密爾頓圖。

　　博薩定理解決了很大一部分的哈密爾頓圖的判定問題，但是依然還存在一定的問題，不滿足博薩定理的圖不一定不是哈密爾頓圖，很多人不斷思索如何改進，很多數(shù)學(xué)家提出了很多種改進方案，但是經(jīng)過比較之后，捷克的數(shù)學(xué)家薩瓦達的結(jié)論脫穎而出。目前為止，薩瓦達定理依舊是一種較好的哈密爾頓圖的判定方法。他的結(jié)論如下。

　　定理4(薩瓦達定理)任意一個n≥3的圖G，且D(G)=(a1,a2,,an)滿足鞋面n的條件：對于每一個小于的整數(shù)i的兩個不等式a1≥i+1，an-1≥n-i，至少2

　　有一個是成立的，那么圖G就一定是哈密爾頓圖。

　　2.2.3補充的一個必要定理

　　薩瓦達定理對哈密爾頓圖的判定做出了很大的改進，讓我們又多了一種簡單的方法，但是依然存在哈密爾頓圖不滿足薩瓦達定理。這個時候我們需要用到一個哈密爾頓圖的必要條件。這個條件敘述如下：

　　定理5(一個判定的必要條件)：設(shè)一個無向圖G=(V,E)是一個哈密爾頓圖，V1是V的一個非空子集，則有P(G-V1)≤|V1|。其中P(G-V1)表示從G中刪除V1得到的連同分支數(shù)。

　　這個條件的必要性可以由一下方法證明：

　　證明：假設(shè)C是圖G中的一條哈密爾頓回路。

　　若V1當(dāng)中的頂點是在C上彼此相鄰的頂點，那么顯然有：

　　P(C-V1)=1≤|V1|;

　　(2) 若V1中的頂點是在C上存在m個互不相鄰，那么就有：

　　P(C-V1)=m≤|V1|

　　所以無論V1中的頂點在C上是相鄰或是不相鄰，或者兼有，都可以得到結(jié)論

　　P(C-V1)≤|V1|

　　同時由于C是圖G的生成子圖，所以可以得到：

　　P(C-V1)≤P(G-V1) ≤|V1|

　　一般時候定理5可以用來判定一個圖是非哈密爾頓圖。

　　判定哈密爾頓圖的方法還有很多，但是最為常用的就是上述的五種方法，當(dāng)然，時至今日，不乏有比這五種方法更為準確全面的方法，但是在這里就不一一介紹了。

　　2.3 實例解析

　　為了能夠讓讀者更好的了解前文介紹的幾種方法，下面舉幾個實例來進行驗證。

　　圖2-1：圖G1、G2

　　在上圖中的兩個圖G1、G2可以簡單的應(yīng)用定理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是哈密爾頓圖。

　　這兩個圖的判定同樣可以應(yīng)用奧勒定理進行判定，在圖G1中任意兩點x、y，有D(x)+D(y)=6≥4;在圖G2中任意兩點x、y，有D(x)+D(y)=8≥6，同樣可以判定圖G1、G2是哈密爾頓圖。

　　圖2-2：圖G3、G4

　　為了更好的體現(xiàn)博薩定理和薩瓦達定理的優(yōu)越性，可以使用圖G3來進行比較。應(yīng)用狄拉克定理時，明顯n=5且D(x)=2≤5/2=n/2，不能判定它是哈密爾頓圖。同樣使用奧勒定理時min(D(x)+D(y))=4≤5/2=n/2，也不能判定。但是簡單的觀察就可以發(fā)現(xiàn)圖G3是一個哈密爾頓圖。這個時候我們就可以用博薩定理進行判定。

　　根據(jù)博薩定理有D(G3)=(2，2，3，3，4)，而P(5)=(1，2，2，3，3)，根據(jù)比較就有D(G3)≥P(5)，從而可以得到圖G3是哈密爾頓圖。

　　同樣也可以根據(jù)薩瓦達定理來進行判定，因為n=5，所以小于n/2的i有i=1、2。

　　當(dāng)i=1時，a1=2≥2=i+1，成立;

　　當(dāng)i=2時，an-1=3≥3=n-i，成立;

　　同樣可以判定圖G3是哈密爾頓圖。

　　然而博薩定理和薩瓦達定理同樣是不完善的，這一點圖G4給我們作出了很好的例子。在應(yīng)用博薩定理時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的正整數(shù)i=1、2、3。當(dāng)i=3時，a1=3≥4=i+1，不成立;an-1=3≥5=n-i，不成立，此時違反薩瓦達定理，所以也不能判定G4是哈密爾頓圖。

　　然而簡單觀察后就可以發(fā)現(xiàn)圖G4是一個哈密爾頓圖，所以博薩定理和薩瓦達定理是有一定的缺陷的。

　　圖G4為我們的進一步研究提供了方向，讓我們能夠不斷的深入。相信在不久的將來會有一種簡單的方法可以幫助我們得出結(jié)論。

　　3 哈密爾頓圖的判定在貨郎擔(dān)問題中的應(yīng)用

　　3.1貨郎擔(dān)問題的由來和在現(xiàn)實中的應(yīng)用

　　貨郎擔(dān)問題是由德國的著名數(shù)學(xué)家肯·蒙那哥在1932年提出來的，80年來一直是哈密爾頓圖的應(yīng)用中的最典型的例子，無數(shù)人對其進行廢寢忘食的研究。這個問題可以表述為：假設(shè)一個售貨員需要在n個城市之間進行銷售，現(xiàn)在我們已經(jīng)知道了這n個城市中任意的兩個城市之間的距離，現(xiàn)在售貨員需要選擇一條路線使得從出發(fā)的城市開始，經(jīng)過其他的城市有且僅有一次，最后回到出發(fā)點，問這個售貨員應(yīng)該怎么樣選擇路線呢。

　　將上述的問題進行數(shù)學(xué)提煉后所求的問題可以轉(zhuǎn)化為，在一個加附了權(quán)值的完全圖中，尋找一個權(quán)值最小的哈密爾頓回路。看似簡單，但實際上卻是非常復(fù)雜的問題，至今任何一種簡化的解決方法都能夠帶來無法想象的價值。因為生活中需要遇到貨郎擔(dān)問題的地方實在是太多了，例如：

　　(1)當(dāng)我們外出旅游的時候，提前安排好路程最短的路線，不僅可以節(jié)省交通上的成本，還可以得到更多的時間來參觀。

　　(2)當(dāng)?shù)卣鸬忍鞛?zāi)發(fā)生時，我們需要組建搜救隊伍對受災(zāi)區(qū)域進行救援，在受災(zāi)程度相近的情況下，安排合適的搜救路線，不僅可以挽回很多的經(jīng)濟損失，更重要的是可以挽救更多的生命。

　　(3)再假設(shè)當(dāng)我們出差坐飛機時，由于各地的情況不同導(dǎo)致各個地方之間的價格會不一樣。我們選擇合適的城市順序，可以讓我們得到大幅度的節(jié)約成本。為公司創(chuàng)造更多的利潤。

　　這類的問題還有很多，而這些問題都可以歸結(jié)為貨郎擔(dān)問題。所以貨郎擔(dān)問題的研究是與生活直接相關(guān)的，是非常具有現(xiàn)實意義的。

　　3.2貨郎擔(dān)問題解決方法

　　那么到底應(yīng)該怎樣去解決貨郎擔(dān)問題呢，遺憾的是直到目前為止，雖然無數(shù)人為止奮斗，也得到了一些正確的結(jié)論，但是還是沒有一種能夠簡單的解決哈密爾頓圖的方法。美國的《管理科學(xué)》中有一篇討論“貨郎擔(dān)問題”的文章，該文中提到：人類由于他的計算能力的限制，在解決貨郎擔(dān)問題上并不好。所以，現(xiàn)在人們對于這個問題的研究已經(jīng)開始借助電子計算機來進行實現(xiàn)。1979年11月7日《紐約時報》上出現(xiàn)了一篇很有影響力的文章，它的標題為《蘇聯(lián)的發(fā)現(xiàn)震動數(shù)學(xué)界》，這篇文章雖然有一定的夸大成分存在，但是他所說的把貨郎擔(dān)問題的解決和計算機聯(lián)系起來的思想確實沒有錯的。2001年廣西大學(xué)計算機與信息工程學(xué)院的羅示豐提出了用計算機判定哈密爾頓圖的方法。雖然這個方法還未應(yīng)用到貨郎擔(dān)問題的解決上，但是卻也堅定了很多人繼續(xù)往這個方向研究的信心，在不久的將來這個問題一定可以獲得更大的突破。

　　德國是一個非常嚴謹?shù)膰�家，德國的波恩大學(xué)的一位數(shù)學(xué)家很好的發(fā)揮了這一特點，當(dāng)他知道西德有120個有鐵路穿過的城市后，就準備找到一個最短路程的回路，應(yīng)該怎么樣去跑。他費盡心血從鐵路局找到了準確的城市間鐵路的長度，把整個問題變成了一個有7140個變數(shù)，120個方程及96個不等式的線性規(guī)劃問

　　題，人類的大腦已經(jīng)對這樣的問題表示無能為力了，最后不得不用電子計算機去算，才得到了最短的回路是6942公里。結(jié)果見圖3-1。

　　圖3-1：西德120個城市最短路線圖

　　3.3樹的搜索法

　　那么在一般情況下我們可以借用什么方法來解決貨郎擔(dān)問題呢?在這里介紹一種較為簡單的方法--------樹的搜索法。

　　為了更好的理解這個方法，在這里我們舉一個例子加以說明：設(shè)共有A、B、

　　C、D、E五個城市，我們需要從A出發(fā)經(jīng)過B、C、D、E四個城市有且僅有一次，最后再回到A。A、B、C、D、E五座城市之間的距離由下表進行表出：

　　圖3-2：五個城市之間的連通情況

　　我們選擇從點A出發(fā)，先寫A(0)，0表示最初沒有出發(fā)路線是的路程長度是0，然后我們可以列出下一步可能到達的城市，分別由B、C、D、E，可以得到四個節(jié)點為AB(10)、AC(20)、AD(50)、AE(70)。見圖3-3。

　　圖3-3：樹的搜索法第一步

　　現(xiàn)在我們可以看到由城市B可能到達的城市有C、D、E，把節(jié)點AB(10)劃掉，我們可以得到三個新的節(jié)點ABC(10+20)、ABD(10+50)、ABE(10+60)后面的20、50、60分別表示BC、BD、BE的長度，以此類推我們還可以得到的新節(jié)點有ACB(40)、ACD(70)、ACE(100)、ADB(100)、ADC(100)、ADE(80)、AEB(130)、AEC(150)、AED(100)九個節(jié)點。見圖3-4。

　　圖3-4：樹的搜索法第二步

　　根據(jù)上述法則繼續(xù)推廣，就可以知道，假設(shè)是ABC的路徑，那么到達C城以后，就只剩下了兩種可能路徑：ABCDEA和ABCEDA，于是我們劃掉節(jié)點ABC(30)，得到兩個新的節(jié)點ABCDEA(180)和ABCEDA(190)。以此類推，我們可以得到其他的二十二個節(jié)點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個城市之間我們一共可以得到二十四條回路，其中最短的兩條為ABEDCA(170)和ACDEBA(170)。由此我們得到了在五個城市之間銷售的最佳路線。

　　做完這全部的工作后，我們回過頭去看這個方法，可以發(fā)現(xiàn)在最后一步的計算時，一部分的工作是可以省略的。比如當(dāng)我們找到第一條回路ABCDEA時，我們可以知道這條路徑的長度是180，那么在之后的計算中，一旦發(fā)現(xiàn)路徑的長度明顯大于180，或者上一層的節(jié)點的數(shù)值已經(jīng)大于180了，那么我們直接可以用“≥180”來代替具體的數(shù)值。當(dāng)計算到ABEDCA這條路徑時，我們發(fā)現(xiàn)數(shù)值是170，那么之后的數(shù)值如明顯大于170，那么久可以用“≥170”來替代，這樣可以節(jié)省一定的計算時間，加快得出結(jié)果的速度。

　　在上面方法展示的過程中我們可以發(fā)現(xiàn)，這樣的搜索方法在地點數(shù)量較少的時候還比較試用，一旦地點數(shù)量達到十個，那么我們的計算量將變的嚇人，甚至可以說是超過了人腦的計算能力，我們會感到十分的繁瑣。如果十個地點還可以

　　勉強算出來，那么地點數(shù)量達到300個或者500個呢?那時候的計算量是我們無法想象的，而這種情況對于像中國這樣的大國來說，是非常現(xiàn)實的問題。這個時候我們就不得不借助計算機的力量。

　　計算機到底可以提升多少的計算速度呢?一個例子能夠很好的說明問題：在美國工作的華籍?dāng)?shù)學(xué)家Lin Shen及Hong Saman等人在1977年的時候用電子計算器計算得到了一個有關(guān)于318個城市的貨郎擔(dān)問題。這個問題一旦化成線性規(guī)劃問題，那么就要處理有50403個變數(shù)的方程式及不等式，人腦對于這樣的問題雖然不能說完全不能解決，但是所需要的時間將是難以想象的。而當(dāng)時的Lin Shen等人借助了一臺IBM的370—168式的電子計算機后，僅用了28.38分鐘就得到了一個最優(yōu)解，納悶對于電子技術(shù)日新月異的今天，我們可能需要的時間已經(jīng)不足一分鐘。兩者互相對比，讓我們不得不承認，以后的發(fā)展方向?qū)⒏�多的借助計算機技術(shù)。

　　4 結(jié)論

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

【哈密爾頓圖的判定及應(yīng)用論文】相關(guān)文章：

波動圖象與振動圖象的綜合應(yīng)用練習(xí)題05-29

學(xué)年判定總結(jié)03-13

關(guān)于高考的試卷怎么判定07-12

《金陵圖》原文及翻譯賞析05-19

背影圖閱讀題及答案10-08

直線與圓的位置關(guān)系判定10-12

頂崗實習(xí)自我判定范文03-17

《背影圖》的閱讀練習(xí)題及答案12-26

古詩絕句《金陵圖》譯文及賞析12-31

書韓干牧馬圖原文及賞析08-16