哈密爾頓圖的判定及應(yīng)用畢業(yè)論文(編輯修改稿)
2025-08-23 06:07 本頁面
【文章內(nèi)容簡介】 點X的通路個數(shù)為D(X)，當圖的每個的頂點的D(X)相當大時，這個圖就是哈密爾頓圖。定理1（狄拉克定理）：對于任意給定的一個圖，如果這個圖的頂點數(shù)，而且，那么這個圖就是哈密爾頓圖。狄拉克發(fā)現(xiàn)上述定理的八年后，經(jīng)過不斷的嘗試和總結(jié)，著名的美國圖論學(xué)家奧斯坦奧勒繼續(xù)了狄拉克的工作，推廣了狄拉克定理，得到了一個判定哈密爾頓圖的基礎(chǔ)結(jié)論，為后面的研究打開了一個方向。定理2（奧勒定理）：對于任意給定的一個圖，如果這個圖的頂點數(shù)，對于任意的兩個頂點x、y有，那么這個圖一定是哈密爾頓圖。 博薩定理和薩瓦達定理在奧勒定理被發(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表示當且僅當對于每一個i=…、n，j=…、n，都滿足xi≥yj。例如：X=（1，2，3，4）； Y=（5，6，7，8）； Z=（6，4，5，3）。 我們可以得到Y(jié)≥X,但是Z≥X卻是錯誤的。 然后我們定義每一個的的整數(shù)得到一個序列P(n)：當n是奇數(shù)時，我們可以將P(n)定義成整數(shù)列：P(n)=（1,2,3,4，…，，，…，），一共包含n個數(shù)。當n是偶數(shù)時，我們可以將P(n)定義成整數(shù)列：P(n)=（1,2,3,4，…，，，…，）一共包含n個數(shù)。根據(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（博薩定理），任意一個的圖，它的D(G)滿足關(guān)系式有D(G)≥P(n),那么圖G就是哈密爾頓圖。博薩定理解決了很大一部分的哈密爾頓圖的判定問題，但是依然還存在一定的問題，不滿足博薩定理的圖不一定不是哈密爾頓圖，很多人不斷思索如何改進，很多數(shù)學(xué)家提出了很多種改進方案，但是經(jīng)過比較之后，捷克的數(shù)學(xué)家薩瓦達的結(jié)論脫穎而出。目前為止，薩瓦達定理依舊是一種較好的哈密爾頓圖的判定方法。他的結(jié)論如下。定理4（薩瓦達定理）任意一個的圖G，且D(G)=（a1,a2,…,an）滿足鞋面的條件：對于每一個小于的整數(shù)i的兩個不等式a1≥i+1，an1≥ni，至少有一個是成立的，那么圖G就一定是哈密爾頓圖。 薩瓦達定理對哈密爾頓圖的判定做出了很大的改進，讓我們又多了一種簡單的方法，但是依然存在哈密爾頓圖不滿足薩瓦達定理。這個時候我們需要用到一個哈密爾頓圖的必要條件。這個條件敘述如下：定理5（一個判定的必要條件）：設(shè)一個無向圖G=(V,E)是一個哈密爾頓圖，V1是V的一個非空子集，則有P(GV1)≤|V1|。其中P(GV1)表示從G中刪除V1得到的連同分支數(shù)。這個條件的必要性可以由一下方法證明：證明：假設(shè)C是圖G中的一條哈密爾頓回路。若V1當中的頂點是在C上彼此相鄰的頂點，那么顯然有：P(CV1)=1≤|V1|；（2） 若V1中的頂點是在C上存在m個互不相鄰，那么就有：P(CV1)=m≤|V1|所以無論V1中的頂點在C上是相鄰或是不相鄰，或者兼有，都可以得到結(jié)論P(CV1)≤|V1|同時由于C是圖G的生成子圖，所以可以得到：P(CV1)≤P(GV1) ≤|V1|一般時候定理5可以用來判定一個圖是非哈密爾頓圖。判定哈密爾頓圖的方法還有很多，但是最為常用的就是上述的五種方法，當然，時至今日，不乏有比這五種方法更為準確全面的方法，但是在這里就不一一介紹了。 實例解析為了能夠讓讀者更好的了解前文介紹的幾種方法，下面舉幾個實例來進行驗證。圖21：圖GG2在上圖中的兩個圖GG2可以簡單的應(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。由此可以判定圖GG2是哈密爾頓圖。這兩個圖的判定同樣可以應(yīng)用奧勒定理進行判定，在圖G1中任意兩點x、y，有D(x)+D(y)=6≥4；在圖G2中任意兩點x、y，有D(x)+D(y)=8≥6，同樣可以判定圖GG2是哈密爾頓圖。圖22：圖GG4為了更好的體現(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=2。當i=1時，a1=2≥2=i+1，成立；當i=2時，an1=3≥3=ni，成立；同樣可以判定圖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=3。當i=3時，a1=3≥4=i+1，不成立；an1=3≥5=ni，不成立，此時違反薩瓦達定理，所以也不能判定G4是哈密爾頓圖。然而簡單觀察后就可以發(fā)現(xiàn)圖G4是一個哈密爾頓圖，所以博薩定理和薩瓦
環(huán)評公示相關(guān)推薦
鄂ICP備17016276號-1