(六)中國郵遞員問題

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

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

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

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

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

6、4v9v8G243469544354G1顯然G1不是最佳方案G1是歐拉圖，第二步：調(diào)整可行方案， 使重復(fù)邊權(quán)和下降重復(fù)邊權(quán)和=若圖中某條邊有兩條或多于兩條的重復(fù)邊同時去掉偶數(shù)條，G2使圖中每一條邊最多有一條重復(fù)邊G2的重復(fù)邊權(quán)和=24346954435步驟1、可得到重復(fù)邊權(quán)和較小的歐拉圖4G2243469544354512124346954435G2是歐拉圖，重復(fù)邊權(quán)和=21G242、使圖中每個初等圈重復(fù)邊的 權(quán)和不大于該圈權(quán)和的一半9個初等圈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是最佳方案奇偶點圖上作業(yè)法：第一步：確

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

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