第4講Euler圖和Hamilton圖

1、下下回回停停1. Euler圖和中國(guó)郵遞員問(wèn)題圖和中國(guó)郵遞員問(wèn)題 2. Fleury算法算法3. Hamilton圖和旅行售貨商問(wèn)題圖和旅行售貨商問(wèn)題 第四講第四講 Euler圖和圖和Hamilton圖圖4. 改良圈算法改良圈算法 一、一、Euler圖和中國(guó)郵遞員問(wèn)題圖和中國(guó)郵遞員問(wèn)題 經(jīng)過(guò)圖的每條邊至少一次的閉跡稱為圖的環(huán)環(huán)游游；經(jīng)過(guò)每條邊僅一次的環(huán)游稱為圖的Euler環(huán)環(huán)游游。包含Euler環(huán)游的圖稱為Euler圖圖。 1973年瑞典數(shù)學(xué)家歐拉解決的柯尼斯堡問(wèn)題，實(shí)質(zhì)就是在圖中尋找一條經(jīng)過(guò)每條邊一次且僅一次的閉跡，推廣這個(gè)問(wèn)題進(jìn)行Euler圖的研究。定理一：當(dāng)定理一：當(dāng)G是連通圖時(shí)，下面三

2、個(gè)命題等價(jià)是連通圖時(shí)，下面三個(gè)命題等價(jià)1.G是是Euler圖圖2.G的每個(gè)頂點(diǎn)是偶次的每個(gè)頂點(diǎn)是偶次3.G是圈的并，且圈的交集是空集是圈的并，且圈的交集是空集 “一筆畫一筆畫”，就是指一筆能畫出的圖形，就是指一筆能畫出的圖形，容易知道，一筆畫其實(shí)就是容易知道，一筆畫其實(shí)就是Euler通路和通路和回路的思想。回路的思想。推論一：一個(gè)連通圖有推論一：一個(gè)連通圖有Euler跡當(dāng)且僅跡當(dāng)且僅當(dāng)最多有兩個(gè)奇點(diǎn)。當(dāng)最多有兩個(gè)奇點(diǎn)。中國(guó)郵遞員問(wèn)題中國(guó)郵遞員問(wèn)題 一位郵遞員從郵局選好郵件去投遞，然后一位郵遞員從郵局選好郵件去投遞，然后回到郵局。他必須經(jīng)過(guò)所管轄的街道至少一次，回到郵局。他必須經(jīng)過(guò)所管轄的街道至

3、少一次，請(qǐng)問(wèn)這位郵遞員如何選擇一條路線，使得所行請(qǐng)問(wèn)這位郵遞員如何選擇一條路線，使得所行路程盡可能的少。這就是中國(guó)郵遞員的原始模路程盡可能的少。這就是中國(guó)郵遞員的原始模型，是我國(guó)管梅谷教授型，是我國(guó)管梅谷教授1962年首先提出并開(kāi)始年首先提出并開(kāi)始研究的。研究的。 如果如果G是是Euler圖，則任何環(huán)游都是最優(yōu)環(huán)圖，則任何環(huán)游都是最優(yōu)環(huán)游，針對(duì)這種情形，游，針對(duì)這種情形，F(xiàn)leury提出一種算法，能提出一種算法，能在在Euler圖中找出環(huán)游。圖中找出環(huán)游。Fleury算法步驟算法步驟1.確定任意一個(gè)起點(diǎn)。確定任意一個(gè)起點(diǎn)。2.若某條行跡已經(jīng)確定，從若某條行跡已經(jīng)確定，從E-e1,e2,ei中選

4、擇中選擇下一條邊，滿足下一條邊，滿足 a。 ei+1與與ei相鄰相鄰 b。除非無(wú)選擇余地，否則。除非無(wú)選擇余地，否則ei+1不是不是G=G- e1,e2,.ei的橋的橋3. 直到步驟直到步驟2不能進(jìn)行為止。不能進(jìn)行為止。二、二、【Fleury算法：見(jiàn)算法：見(jiàn)word文檔文檔】 三、三、HamiltonHamilton圈和圈和旅行售貨商問(wèn)題旅行售貨商問(wèn)題 1859年，數(shù)學(xué)家Hamilton發(fā)明了一種周游世界的游戲。把一個(gè)12面體的20個(gè)頂點(diǎn)分別標(biāo)上北京、東京、華盛頓等20個(gè)大都市的名字，要求玩的人從某城市出發(fā)，沿著12面體的棱通過(guò)每一個(gè)城市恰好一次，再回到出發(fā)的城市。這種游戲在歐洲曾經(jīng)風(fēng)靡一時(shí)，

5、Hamilton以25個(gè)金幣的高價(jià)把該項(xiàng)專利賣給了一個(gè)玩具商。 用圖論的語(yǔ)言來(lái)講，此游戲本質(zhì)就是在一個(gè)12面體上尋找經(jīng)過(guò)每一個(gè)頂點(diǎn)一次且恰好一次的特殊的圈，即Hamilton回路。 與歐拉圖的情形相反，到目前為止，判斷與歐拉圖的情形相反，到目前為止，判斷Hamilton圈非平凡的充分必要條件尚不清楚；圈非平凡的充分必要條件尚不清楚；事實(shí)上，這是圖論尚未解決的主要問(wèn)題之一。事實(shí)上，這是圖論尚未解決的主要問(wèn)題之一。一名旅行售貨員想去訪問(wèn)若干村，最后回到他的一名旅行售貨員想去訪問(wèn)若干村，最后回到他的出發(fā)地。給定各村之間所需的旅行時(shí)間，應(yīng)該怎出發(fā)地。給定各村之間所需的旅行時(shí)間，應(yīng)該怎樣計(jì)劃他的路線，使

6、得這位售貨員能對(duì)每個(gè)村進(jìn)樣計(jì)劃他的路線，使得這位售貨員能對(duì)每個(gè)村進(jìn)行一次訪問(wèn)而總時(shí)間最短？這個(gè)問(wèn)題就是著名的行一次訪問(wèn)而總時(shí)間最短？這個(gè)問(wèn)題就是著名的旅行售貨員問(wèn)題，或者叫做貨郎擔(dān)問(wèn)題。旅行售貨員問(wèn)題，或者叫做貨郎擔(dān)問(wèn)題。 首先給出求近似最優(yōu)首先給出求近似最優(yōu)Hamilton圈的最鄰近算圈的最鄰近算法的基本思想：法的基本思想： 針對(duì)旅行售貨商問(wèn)題，給出較好的近似算法，針對(duì)旅行售貨商問(wèn)題，給出較好的近似算法，即最臨近算法和一個(gè)修改算法。設(shè)即最臨近算法和一個(gè)修改算法。設(shè)n個(gè)頂點(diǎn)的賦值個(gè)頂點(diǎn)的賦值完全圖為完全圖為G，W為權(quán)值矩陣。根據(jù)實(shí)際問(wèn)題，可為權(quán)值矩陣。根據(jù)實(shí)際問(wèn)題，可以假設(shè)以假設(shè)w(uv)+w

7、(vx)=w(ux). 結(jié)合圖論知識(shí)，上述貨郎擔(dān)問(wèn)題本質(zhì)就是在賦結(jié)合圖論知識(shí)，上述貨郎擔(dān)問(wèn)題本質(zhì)就是在賦權(quán)完全圖中，找出一個(gè)最小權(quán)的權(quán)完全圖中，找出一個(gè)最小權(quán)的Hamilton圈，此圈，此圈稱為最優(yōu)圈。與最短路問(wèn)題相反，至今尚未有求圈稱為最優(yōu)圈。與最短路問(wèn)題相反，至今尚未有求解旅行售貨商問(wèn)題的有效算法，因此，在這里只試解旅行售貨商問(wèn)題的有效算法，因此，在這里只試圖找出較好的解，但不一定是最優(yōu)解。圖找出較好的解，但不一定是最優(yōu)解。1.任選一頂點(diǎn)任選一頂點(diǎn)V0為起點(diǎn)，找一條與為起點(diǎn)，找一條與V0關(guān)聯(lián)且關(guān)聯(lián)且權(quán)最小的邊權(quán)最小的邊e1,e1的另一個(gè)頂點(diǎn)是的另一個(gè)頂點(diǎn)是V1.得一條得一條路路V0V1;2

8、.若已選出路若已選出路V0V1Vi,在剩下的點(diǎn)中選取一在剩下的點(diǎn)中選取一個(gè)與個(gè)與Vi最近的相鄰點(diǎn)最近的相鄰點(diǎn)Vi+1得新的路；得新的路；3.若若i+1n-1,用用i代替代替i+1，返回，返回2； 否則，記否則，記C=V0V1VpV0.停止停止【最鄰近算法思想【最鄰近算法思想】 四、改良圈算法四、改良圈算法 假設(shè)已經(jīng)找到假設(shè)已經(jīng)找到G的一個(gè)的一個(gè)Hamilton圈圈V1V2VnV1. 對(duì)圈中所有滿足對(duì)圈中所有滿足1i+1jV的的i,j，按照以下方法尋，按照以下方法尋找新的找新的Hamilton圈。圈?！舅惴ㄋ枷搿舅惴ㄋ枷搿?. 在圈中尋找在圈中尋找i不等于不等于j,使得使得ViVj,Vi+1,V

9、j+1在圈在圈中，且中，且W(ViVj)+W(Vi+1Vj+1)W(ViVi+1)+W(VjVj+1) 則構(gòu)成新的圈則構(gòu)成新的圈.2. 用新圈代替舊圈，直至終止。用新圈代替舊圈，直至終止?！舅惴ǖ摹舅惴ǖ腗atlab程序】見(jiàn)程序】見(jiàn)word文檔文檔例：給定四個(gè)點(diǎn)例：給定四個(gè)點(diǎn)(0,0),(100,1000),(0,2),(1000,0),用改良圈算用改良圈算法計(jì)算經(jīng)過(guò)這四個(gè)點(diǎn)的法計(jì)算經(jīng)過(guò)這四個(gè)點(diǎn)的Hamilton圈。圈。V= 0 0 ;100 1000; 0 2; 1000 0For i=1：4 for j=1:4 W(i,j)=sqrt(V(i,1)-V(j,1)2+(V(i,2)-V(j,2)2); endend第四講習(xí)題：第四講習(xí)題：1.判斷圖判斷圖1是否是歐拉圖，若是，求是否是歐拉圖，若是，求Euler回路。回路。2.給定給定10個(gè)點(diǎn)的坐標(biāo)個(gè)點(diǎn)的坐標(biāo)(5,67),(37,8),(4