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

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

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