(六)中國(guó)郵遞員問(wèn)題

1、Euler circuit and Chinese Postman Problem 歐拉回路和中國(guó)郵遞員問(wèn)題歌尼斯堡七橋難題普萊格爾河結(jié)論：不存在這樣一種走法。用A、B表示兩座小島，C、D表示兩岸，連線AB表示A、B之間有一座橋。問(wèn)題簡(jiǎn)化為：ABCD在該圖中，從任一點(diǎn)出發(fā)，能否通過(guò)每條線段一次且僅僅一次后又回到原來(lái)的出發(fā)點(diǎn)七橋問(wèn)題的數(shù)學(xué)模型：類(lèi)似的問(wèn)題：一筆畫(huà)問(wèn)題字的一筆畫(huà)：如“中、日、口、串”等可一筆畫(huà)而：“田、目”等不能一筆畫(huà)圖的一筆畫(huà)：可一筆畫(huà)不可一筆畫(huà)6.6.1 歐拉圖與中國(guó)郵遞員問(wèn)題開(kāi)鏈一筆畫(huà)問(wèn)題圈存在歐拉回路：該圖特點(diǎn)：該圖不存在歐拉回路 歐拉圖定理 無(wú)向連通圖G為歐拉圖的 充要條

2、件是G中無(wú)奇點(diǎn)已知G=（V,E)為歐拉圖，即存在一條歐拉回路C，C經(jīng)過(guò)G的每一條邊，由于G為連通圖，所以G中的每個(gè)點(diǎn)至少在C中出現(xiàn)一次證明：必要性充分性：若無(wú)向連通圖G=(V,E)中無(wú)奇點(diǎn)，則G為歐拉圖例：例：判斷下圖是否為歐拉圖，若是，求出歐拉回路推論 無(wú)向連通圖G有歐拉道路的充要條件 是G中恰有兩個(gè)奇點(diǎn)一筆畫(huà)問(wèn)題：1、一個(gè)連通圖的頂點(diǎn)都是偶點(diǎn)，沒(méi)有奇點(diǎn)，則該圖 可以一筆畫(huà)出2、一個(gè)連通圖的頂點(diǎn)恰有兩個(gè)奇點(diǎn)，其余均為偶點(diǎn)， 則從任一奇點(diǎn)出發(fā)，可以一筆畫(huà)出該圖，而終點(diǎn) 則是另一個(gè)奇點(diǎn)。（從任一點(diǎn)出發(fā)均可）3、一個(gè)連通圖的頂點(diǎn)有兩個(gè)以上的奇點(diǎn)，則該圖 不能一筆畫(huà)出田日中白回不連通可一筆畫(huà)可一筆畫(huà)

3、不可一筆畫(huà)可一筆畫(huà)可一筆畫(huà)不可一筆畫(huà)不可一筆畫(huà)6.6.2 中國(guó)郵路問(wèn)題提出問(wèn)題的人：管梅谷教授時(shí)間：1962年提出的問(wèn)題：一個(gè)郵遞員從郵局出發(fā)分送郵件，要走完他負(fù)責(zé)投遞的所有街道，最后再返回郵局，應(yīng)如何選擇投遞路線，才能使所走的路線最短？郵路問(wèn)題的圖論描述：取一無(wú)向賦權(quán)連通圖G=（V，E）E中的每一條邊對(duì)應(yīng)一條街道每條邊的非負(fù)權(quán)l(xiāng)(e)=街道的長(zhǎng)度V中某一個(gè)頂點(diǎn)為郵局，其余為街道的交叉點(diǎn)在G上找一個(gè)圈，該圈過(guò)每邊至少一次，且圈上所有邊的權(quán)和最小1、若G中的頂點(diǎn)均為偶點(diǎn)，即G中存在歐拉回路，則該回路過(guò)每條邊一次且僅一次，此回路即為所求的投遞路線郵路問(wèn)題的圖論描述：在無(wú)向連通賦權(quán)G =（V，E）上

4、找一個(gè)圈，該圈過(guò)每邊至少一次，且圈上所有邊的權(quán)和最小2、G中有奇點(diǎn)：不存在歐拉回路投遞路線：至少有一街道要重復(fù)走一次或多次即不存在每條街道走一次且只走一次的投遞路線分析：重復(fù)邊結(jié)論：選擇最佳投遞路線=選擇重復(fù)邊的權(quán)和最小的路線111111111111111111111111111反之，對(duì)郵路圖G，對(duì)該鏈上的每一條邊增加一條重復(fù)邊111111111111111111投遞路線歐拉圖結(jié)論：對(duì)任意一個(gè)含奇點(diǎn)的郵路圖G，由于奇點(diǎn)的個(gè)數(shù)為偶數(shù)個(gè)，把每?jī)蓚€(gè)配成一對(duì)，由于G為連通圖，每對(duì)奇點(diǎn)之間至少存在一條鏈，對(duì)該條鏈上的每一條邊增加一條重復(fù)邊，可得一歐拉圖，該歐拉圖對(duì)應(yīng)一條投遞路線尋找最佳投遞路線方法：在原

5、郵路圖上增加一些重復(fù)邊得一個(gè)歐拉圖，在所得歐拉圖上找出一條歐拉回路。計(jì)算重復(fù)邊的權(quán)和，重復(fù)邊權(quán)和最小歐拉回路既為所求的最佳投遞路線管梅谷奇偶點(diǎn)圖上作業(yè)法奇偶點(diǎn)圖上作業(yè)法：例：求解右圖所示的郵路問(wèn)題第一步：確定一個(gè)初始可行方案方法：檢查圖G中是否有奇點(diǎn)無(wú)奇點(diǎn)： ，找出一條以v1為起點(diǎn)的歐拉回路 ，該回路就是最佳投遞路線有奇點(diǎn)：圖G已是歐拉圖把所有奇點(diǎn)兩兩配成一對(duì)，每對(duì)奇點(diǎn)找一條鏈，在該條鏈上的每一條邊增加一條重復(fù)邊，得一個(gè)歐拉圖G1， 由G1所確定的歐拉回路即為一個(gè)可行方案v2，v8，v4，v6G中有奇點(diǎn)：取v2到v4的一條鏈：v2v1v6v7v8v9v4取v6到v8的一條鏈：v6v1v2v3v

6、4v9v8G243469544354G1顯然G1不是最佳方案G1是歐拉圖，第二步：調(diào)整可行方案， 使重復(fù)邊權(quán)和下降重復(fù)邊權(quán)和=若圖中某條邊有兩條或多于兩條的重復(fù)邊同時(shí)去掉偶數(shù)條，G2使圖中每一條邊最多有一條重復(fù)邊G2的重復(fù)邊權(quán)和=24346954435步驟1、可得到重復(fù)邊權(quán)和較小的歐拉圖4G2243469544354512124346954435G2是歐拉圖，重復(fù)邊權(quán)和=21G242、使圖中每個(gè)初等圈重復(fù)邊的 權(quán)和不大于該圈權(quán)和的一半9個(gè)初等圈24346954435G24G3G3是歐拉圖，重復(fù)邊權(quán)和=17G32434695443546（1）v1v2v5v6v1167（2）v6v5v8v7v61

7、410（3）v2v3v4v5v2244（4）v5v4v9v8v516G3的初等圈權(quán)和重復(fù)邊權(quán)和13（5）v1v2v5v8v7v6v124G4243469544354G42434695443547（1）v1v2v5v6v1164（2）v6v5v8v7v6144（3）v2v3v4v5v2248（4）v5v4v9v8v516G4的初等圈權(quán)和重復(fù)邊權(quán)和11（5）v1v2v5v8v7v6v124（6）v2v3v4v9v8v5v2324（8）v6v5v4v9v8v7v6（7）v1v2v3v4v5v6v12811224（9）v1v2v3v4v9v8v7v6v1367G4是最佳方案奇偶點(diǎn)圖上作業(yè)法：第一步：確

8、定一個(gè)初始可行方案方法：檢查圖G中是否有奇點(diǎn)。無(wú)奇點(diǎn)：，找出一條以v0為起點(diǎn)的歐拉回路，該回路就是最佳投遞路線有奇點(diǎn)：圖G已是歐拉圖把所有奇點(diǎn)兩兩配成一對(duì)，每對(duì)奇點(diǎn)找一條鏈，在該條鏈上的每一條邊增加一條重復(fù)邊第二步：調(diào)整可行方案，使重復(fù)邊權(quán)和下降1、使圖中每一條邊最多有一條重復(fù)邊若圖中某條邊有兩條或多于兩條的重復(fù)邊，同時(shí)去掉偶數(shù)條2、使圖中每個(gè)初等圈重復(fù)邊的權(quán)和該圈權(quán)和的一半若圖中某初等圈重復(fù)邊的權(quán)和大于該圈權(quán)和的一半去掉圈中的重復(fù)邊同時(shí)將圈中沒(méi)有重復(fù)邊的邊加上重復(fù)邊2326154231223261542312最佳投遞路線：v0v3v0V4v3v4v5v3v2v523261542312v1v2

9、v1v4v1v0說(shuō)明: 關(guān)于中國(guó)郵遞員問(wèn)題的有效算法由Edmonds和Johnson1973年給出。 J.Edmonds，E. L. Johnson. Matching Euler tours and the Chinese postman. Mathematical Programming, 1973, 5: 88-124小結(jié): 會(huì)用閉圈法和破圈法求最小支撐樹(shù) 會(huì)用Dijkstra算法求兩點(diǎn)間的最短路徑 會(huì)求最大流和最小截集 會(huì)解最小費(fèi)用最大流問(wèn)題 內(nèi)容總結(jié)Euler circuit and。Chinese Postman Problem。用A、B表示兩座小島，C、D表示兩岸，。在該圖中，從任一點(diǎn)出發(fā)，能否通過(guò)每條線段一次且僅僅一次后又回到原來(lái)的出發(fā)點(diǎn)。類(lèi)似的問(wèn)題：一筆畫(huà)問(wèn)題。字的一筆畫(huà)：如“中、日、口、串”等可一筆畫(huà)。6.6.1 歐拉圖與中國(guó)郵遞員問(wèn)題。定理 無(wú)向連通圖G為歐拉圖的。已知G=（V,E)為歐拉圖，即存在一條歐拉回路C，。所以G中的每個(gè)點(diǎn)至少在C中出現(xiàn)一次。若無(wú)向連通圖G=(V,E)中無(wú)奇點(diǎn)，則G為歐拉圖。例：判斷下圖是否為歐拉圖，若是，求出歐拉回路。