淺談圖論在數(shù)學(xué)中的應(yīng)用

淺談圖論在數(shù)學(xué)中的應(yīng)用

1周游世界游戲哈默爾頓是一位在愛蘭治的哲學(xué)家和哲學(xué)家。他的生活非常豐富多彩。在他發(fā)現(xiàn)“四元數(shù)”后，他發(fā)現(xiàn)了另一種被稱為“代碼系統(tǒng)”的代際系統(tǒng)。該系統(tǒng)包含大乘和加法的算術(shù)算子，但大乘和語法不符合交換法。他發(fā)現(xiàn)的這個代數(shù)系統(tǒng)是和正則12面體有關(guān)的.于是在1859年他提出了所謂的“周游世界游戲”:將一個正十二面體當(dāng)中的20個頂點分別表示全世界的20個城市(如圖1-1),一個人要從其中的某一個城市出發(fā),經(jīng)過每一個城市剛好一次,然后再回到出發(fā)點,問這樣的旅行路線是否真的存在?這個游戲曾經(jīng)風(fēng)靡一時.可以應(yīng)用拓?fù)涞乃枷?將這正十二面體“拉平”將會得到一個和它同構(gòu)的平面圖(如圖1-2),這樣進(jìn)行就可以將這個游戲轉(zhuǎn)化為:要求必須沿著正十二面體的棱,怎樣才能走完正則十二面體上的所有頂點,而且最后又回到起點的問題.從此以后,由于這游戲的緣故,人們就把這一類圖稱為哈密爾頓圖.2哈密爾頓回路圖g設(shè)G是一個圖,包含圖G中的每個頂點的路就稱為哈密爾頓路.通過圖G中每個頂點有且僅有一次的通路就稱為哈密爾頓通路.通過圖G中的每個頂點有且僅有一次的回路就稱為哈密爾頓回路.一個圖假如含有哈密爾頓回路,則這個圖就是哈密爾頓圖.3哈密爾頓圖的圖任意給定一個圖,怎樣才能知道它是不是哈密爾頓圖呢?當(dāng)然如果這個圖的頂點不多,你可以直接用最為古老的“嘗試和錯誤”的蠻力方法找出哈密爾頓回路就可以判斷了.但是數(shù)學(xué)家們并不滿意這種碰得焦頭爛額后才能找到真理的辦法.那么是否存在一個充分必要條件,能使我們簡單地判斷任意給的圖是否為哈密爾頓圖呢?很多科學(xué)家做過大量研究,但是遺憾的是到目前為止還沒能得到一個判別哈密爾頓圖的充要條件,這也是圖論的一大難題.雖然存在一些充分不必要,或者必要不充分的條件,但是在大部分的情況下,還是采用最古老的嘗試的辦法,不過這些判別方法在某些場合也是十分有用的.下面將介紹幾個判別哈密爾頓圖的方法:因為對任意一個圖來說如果它是哈密爾頓圖,當(dāng)且僅當(dāng)它的基礎(chǔ)簡單圖是哈密爾頓圖,所以我們只要考慮簡單圖.我們首先給出判別哈密爾頓圖的四個充分條件:最早的提出哈密爾頓圖的充分條件的是英國的狄拉克.他的定理只要求檢查圖上的每個頂點x,看每個頂點x上有多少個弧通過,將通過頂點x的弧個條數(shù)記為D(x),當(dāng)圖中的每個頂點的D(x)相當(dāng)大時,這個圖就是哈密爾頓圖.定理1(狄拉克定理)任意給定一個圖,如果這個圖的頂點數(shù)n≥3,而且D(x)≥n/2,那么這個圖一定是哈密爾頓圖.根據(jù)狄拉克定理我們可以判斷下面的兩個圖G1和G2(圖2-1)都是哈密爾頓圖.因為在圖G1當(dāng)中,每一個頂點x都有D(x)=3,而n=4,顯然D(x)=3≥4/2=2.而在圖G2當(dāng)中,每一個頂點x都有D(x)=4,而n=6,顯然D(x)=4≥6/2=2.所以圖G1和圖G2都是哈密爾頓圖.在狄拉克提出上述充分條件的八年后,美國的著名圖論學(xué)家奧斯坦·奧勒將狄拉克的工作進(jìn)行了推廣,得到了以下的十分重要的結(jié)論.定理2(奧勒定理)任意給定一個圖,如果這個圖的頂點數(shù)n≥3,而且對于任意的兩個頂點x,y都有D(x)+D(y)≥n,那么這個圖一定是哈密爾頓圖.在奧勒得到上述結(jié)論兩年后,匈牙利的一個叫博薩德的少年發(fā)表了僅有一頁長的論文,雖然論文只有一頁但其結(jié)果卻對奧勒定理進(jìn)行了推廣,他所做的工作是相當(dāng)重要的,在當(dāng)時引起了很多人的關(guān)注.在以后的幾年中,有很多的人都想改進(jìn)他的工作,最后有一個捷克的青年數(shù)學(xué)家得到了比他更好的結(jié)論.為了更好的看清博薩的結(jié)論,在這里先引進(jìn)一些記號:對于任意的一個圖G,我們用D(G)表示序列(D(x1),D(x2),…,D(xn)),這里的x1,x2,…,xn代表圖G中的所有頂點,而序列的數(shù)是由小到大的排列,也就是說D(x1)≤D(x2)≤…≤D(xn).例如在圖2-1中我們有:假設(shè)有以下的兩個序列其具有相同個數(shù)的數(shù)字:我們用X≥Y表示當(dāng)且僅當(dāng)對于每一個i=1,2,…,n,都滿足xi≥yi.例如:我們就可以得到X≥Y,但X≥Z就是錯誤的.下面對于每一個n≥3的整數(shù),我們定如下義整數(shù)序列P(n):(1)如果n是奇數(shù),我們就可以將P(n)定義成如下的整數(shù)列:(2)如果n是偶數(shù),我們就可以將P(n)定義成如下的整數(shù)列:根據(jù)上述定義我們就有下面就可以闡述博薩德重要發(fā)現(xiàn)了:定理3(博薩定理)要是一個有n≥3的圖,它的D(G)滿足不等式D(G)≥P(n),那么圖G就是哈密爾頓圖.我們來看圖2-2:我們很容易的就可以發(fā)現(xiàn):D(G3)=(2,2,3,3,4);D(G4)=(3,3,3,3,3,3,3,3).他們都是哈密爾頓圖,但是圖G3并不滿足奧勒的條件,因為:可是我們卻可以得到從上面的分析可以看出博薩的結(jié)論比奧勒的結(jié)論要強(qiáng).但是我們卻通過圖G4看到了它并不滿足博薩的不等式.所以人們?nèi)藗兙蛧L試著想找出比博薩更好的不等式來判別更加多的哈密爾頓圖.到目前為止,比較好的結(jié)論是捷克的青年數(shù)學(xué)家薩瓦達(dá)提出來的,他的結(jié)論如下:定理4(薩瓦達(dá)定理)如果一個圖G的頂點數(shù)大于2,而且D(G)=(a1,a2,…,an)滿足下面的條件:對于每一個小于n/2的正整數(shù)i兩個不等式ai≥i+1,an-i≥n-i最少有一個是成立的,那么圖G就一定是哈密爾頓圖.我們可以看出圖G4并不滿足薩瓦達(dá)條件,所以我們可以相信有更好的條件存在.我們下面給出一個判別哈密爾頓圖的必要條件:定理5設(shè)一個無向圖G=(V,E)是一個哈密爾頓圖,V1是V的一個非空子集,則有P(G-V1)≤|V1|.其中P(G-V1)表示從G中刪除V1后得到的連同分支數(shù).證明假設(shè)C為圖G當(dāng)中的一條哈密爾頓回路.(1)要是V1當(dāng)中的頂點在C上是彼此相鄰的,那么:(2)要是V1當(dāng)中的頂點在C上存在R(2≤R≤|V1|)個互相不相鄰,那么:對于一般的來說,V1當(dāng)中的頂點在C上總是既有相鄰的又有不相鄰的,因而總會有:又因為C為圖G的生成子圖,所以:定理5一般是用來證明某一個圖是非哈密爾頓圖的.以上是目前判斷一個圖是否是哈密爾頓圖的幾種常用的方法.判斷一個圖是否是哈密爾頓圖的其它方法,限于篇幅就不一一介紹了.4從“旅行貨郎問題”求解假設(shè)有n個城鎮(zhèn),已知其中任意的兩個城鎮(zhèn)間的距離,一個售貨員,要從某一個城鎮(zhèn)出發(fā)巡回售貨,問這個售貨員應(yīng)該怎樣的選擇路線,才能使每個城鎮(zhèn)有且只有經(jīng)過一次,最后又回到出發(fā)點,并且要使總的行程最短.這個問題就稱為旅行貨郎問題.實際旅行貨郎問題就是指在一個賦了權(quán)的完全圖當(dāng)中,找出一個具有最小權(quán)值的哈密爾頓路,最后回到出發(fā)地.旅行貨郎問題是由德國的著名數(shù)學(xué)家K.Menger在1932年提出來的,近80年來一直是很多人廢寢忘食的研究對象.在我們的日常生活當(dāng)中常常會遇到這樣的問題,例如:(1)假設(shè)你是一個學(xué)校校車的司機(jī),要從學(xué)校開車出來,到不相同的街道去接學(xué)生,你應(yīng)該怎樣安排線路才能使開車的路程最短,可以接到所有的學(xué)生回到學(xué)校?(2)假設(shè)你你需要乘坐飛機(jī)去幾個城市,而不同的飛機(jī)公司會提供不相同的票價,你應(yīng)該怎樣的安排行程,使得你能走遍你將要去的城市,最后又回到你最開始所在的地點,而且又能最省錢?(3)假設(shè)你想自己駕車去幾個城市旅行,但現(xiàn)在的汽油價格這么的昂貴,你想盡量多的省油,而汽油的消耗跟路程是稱正比的,因此就得想個辦法找到一個回路,這個回路應(yīng)該有最短的路程.上述的這些問題,從表面上看并沒有什么的關(guān)系,但實質(zhì)上它們都可以歸結(jié)從“旅行貨郎問題”來求解.雖然現(xiàn)實當(dāng)中的很多問題都可以歸結(jié)為“旅行貨郎問題”,但是到目前為此,還沒有找到一個行之有效的求解方案.“旅行貨郎問題”目前是很多的國家(例如美國、日本、德國、法國、中國)的運(yùn)籌學(xué)工作者的研究熱點.雖然現(xiàn)在解決“旅行貨郎問題”有很多種方法,但是由于這些好的辦法都要牽涉到很深的數(shù)學(xué)知識,所以在這就不做介紹了.結(jié)論:圖論是一門古老而又年輕的學(xué)科.伴隨著科學(xué)技術(shù)的蓬勃發(fā)展,圖論的知識已經(jīng)滲透