1、會計學1 六中國郵遞員問題六中國郵遞員問題 歌尼斯堡七橋難題 普萊格爾河 第1頁/共38頁 結論：不存在這樣一種走法。 用A、B表示兩座小島，C、D表示兩岸， 連線AB表示A、B之間有一座橋。 問題簡化為： A B C D 在該圖中，從任一點出發，能否通過每條線段 一次且僅僅一次后又回到原來的出發點 七橋問題的數學模型： 第2頁/共38頁 類似的問題：一筆畫問題 字的一筆畫：如“中、日、口、串”等可一筆畫 而：“田、目”等不能一筆畫 圖的一筆畫： 可一筆畫不可一筆畫 第3頁/共38頁 6.6.1 歐拉圖與中國郵遞員問題 歐拉道路： 道路，則稱這條道路為歐拉每一條邊一次且僅一次 中的存在一條道路

2、，經過是一個無向連通圖，若設GG 開 鏈 , 4456223345112 vevevevevevev 一條歐拉道路： 的到存在 42 vv 一條歐拉道路： 的到存在 43 vv , 441122433 vevevevev 1 e 2 e 3 e 4 e 1 v 2 v 3 v 4 v 1 e 2 e 3 e 4 e 5 e 6 e 1 v 2 v 3 v 4 v 5 v 1 e 3 e 2 e 1 v 2 v 3 v 4 v 任兩點之間都不 存在歐拉道路 一筆畫問題 第4頁/共38頁 回路，則稱這個回路為歐拉每一條邊一次且僅一次 中的存在一個回路，經過是一個無向連通圖，若設GG 歐拉回路：圈

3、, 164455274332211 vevevevevevevev 存在歐拉回路： 該圖特點 ： 均為偶數)( i vd 該圖不存在歐拉回路 存在奇點 1 v 2 v 1 e 2 e 3 e 4 e 5 e 3 v 4 v 5 v 6 e 7 e 1 e 2 e 3 e 4 e5 e 1 v 2 v 3 v 4 v 歐拉圖 第5頁/共38頁 定理 無向連通圖G為歐拉圖的 充要條件是G中無奇點 已知G=（V,E)為歐拉圖，即存在一條歐拉回路C， C經過G的每一條邊， 由于G為連通圖， 所以G中的每個點至少在C中出現一次 證明：必要性 Vvi對 的中間點，是若Cvi條邊每出現一次，必關聯兩 i v

4、 , 111132211 vvevevvevevC iiiii ：如 為偶數)( i vd為偶點，即 i v 的起點，是若Cvi的終點，也是 Cvi必關聯兩條邊 i v 為偶數)( i vd為偶點，即 i v 第6頁/共38頁 充分性： 若無向連通圖G=(V,E)中無奇點，則G為歐拉圖 1 e 2 e 3 e 4 e 5 e 6 e 1 v 2 v 3 v 4 v 5 v 6 v 7 e 8 e 9 e 10 e 為偶數)( i vd連通，G G 例： 第7頁/共38頁 1 e 2 e 3 e 4 e 5 e 6 e 1 v 2 v 3 v 4 v 5 v 6 v 7 e 8 e 9 e 10

5、 e , 32294331 vevevevC ：簡單回路 ），（記EVCGG 1 中邊的端點是，EVEEE 1 G 6 v 1 e 4 e 5 e 6 e 1 v 2 v 4 v 5 v 7 e 8 e 10 e G , 21166551022 vevevevevC ：簡單回路 4 e 1 v 4 v 5 v 7 e 8 e G , 18445713 vevevevC ：簡單回路 ，任取一點，如 3 v 221 CvCGG為起點取一個簡單回路的公共頂點與中，以在 13 Cv 為起點的一個簡單回路找一個以 ），（記EVCGG 2 中邊的端點是，EVEEE 1 312 CvCGG為起點取一個簡單回

6、路的公共頂點與中，以在 第8頁/共38頁 1 e 2 e 3 e 4 e 5 e 6 e 1 v 2 v 3 v 4 v 5 v 6 v 7 e 8 e 9 e 10 e G 6 v 1 e 4 e 5 e 6 e 1 v 2 v 4 v 5 v 7 e 8 e 10 e G 2116655102 ,vevevevev 184457 ,veveve, 9433 evev, 32 ve 4 e 1 v 4 v 5 v 7 e 8 e G , 32294331 vevevevC ：簡單回路 , 21166551022 vevevevevC ：簡單回路 , 18445713 vevevevC ：簡單

7、回路 ，得一簡單回路點處插入的從把CCvCC 2123 ，即得所求歐拉回路：點處插入的從再把 121 CvCC , 2116655102 vevevevevC： 184457 ,veveve 第9頁/共38頁 1 e 2 e 3 e 4 e 5 e 6 e 1 v 2 v 3 v 4 v 5 v 7 e 例：判斷下圖是否為歐拉圖，若是，求出歐拉回路 : 1 C 3455473 ,vevevev 164332211 ,vevevevev :歐拉回路 1643 ,veve , 32211 vevev 4 e 5 e 3 v 4 v 5 v 7 e : 2 C 345547 ,veveve 第10頁

8、/共38頁 推論 無向連通圖G有歐拉道路的充要條件 是G中恰有兩個奇點 ),( ji vveG上增加一條邊在 的奇點，是證明：充分性：設Gvv ji, ，得連通圖G 中無奇點，則GCG 存在歐拉回路所以 ，中的邊去掉eC為終點的歐拉道路為起點即得以 ji vv, LvvG ji 為終點的歐拉道路為起點有一條以必要性：設, ),( ji vveG上增加一條邊在 CGLe的一條歐拉回路中得加到把邊為歐拉圖，即G Gvvd,)(為偶數 為奇數)(),(, ji vdvd中，在G 第11頁/共38頁 一筆畫問題： 1、一個連通圖的頂點都是偶點，沒有奇點，則該圖 可以一筆畫出 2、一個連通圖的頂點恰有兩

9、個奇點，其余均為偶點， 則從任一奇點出發，可以一筆畫出該圖，而終點 則是另一個奇點。 （從任一點出發均可） 3、一個連通圖的頂點有兩個以上的奇點，則該圖 不能一筆畫出 第12頁/共38頁 田日中白 回 不連通 可一筆畫可一筆畫不可一筆 畫 可一筆畫 可一筆畫 不可一筆畫不可一筆畫 第13頁/共38頁 6.6.2 中國郵路問題 提出問題的人：管梅谷教授 時間：1962年 提出的問題： 一個郵遞員從郵局出發分送郵件，要走完他負責 投遞的所有街道，最后再返回郵局，應如何選擇 投遞路線，才能使所走的路線最短？ 郵路問題的圖論描述： 取一無向賦權連通圖G=（V，E） E中的每一條邊對應一條街道 每條邊的

10、非負權l(e)=街道的長度 V中某一個頂點為郵局，其余為街道的交叉點 在G上找一個圈， 該圈過每邊至少 一次，且圈上所 有邊的權和最小 第14頁/共38頁 1、若G中的頂點均為偶點 ，即G中存在歐拉回路， 則該回路過每條邊一次且僅一次， 此回路即為所求的投遞路線 郵路問題的圖論描述： 在無向連通賦權G =（V，E）上找一個圈， 該圈過每邊至少一次，且圈上所有邊的權和最小 2、G中有奇點： 不存在歐拉回路 投遞路線：至少有一街道要重復走一次或多次 第15頁/共38頁 為郵局為郵路圖，其中例：設 1 vG 不是歐拉圖為奇數Gvdvd,)(),( 43 不存在歐拉回路，G 即不存在每條街道走一次且只

11、走一次的投遞路線 14253214563211 vvvvvvvvvvvvvC ：路線 12權和 1232563542412 vvvvvvvvvvvvC ：路線 11權和 12 CC 優于路線路線 分析： ），），（，），（，重復走過邊：（路線 4132211 vvvvvvC ），），（，重復走過邊：（路線 32422 vvvvC 重復邊 2重復邊的權和 結論： 選擇最佳投遞路線=選擇重復邊的權和最小的路線 3重復邊的權和 1 v 2 v 3 v 4 v 5 v 6 v 11 1 1 1 1 1 1 1 第16頁/共38頁 1 v 2 v 3 v 4 v 5 v 6 v 11 1 1 1 1 1

12、 1 1 14253214563211 vvvvvvvvvvvvvC ：對路線 ），），（，），（，重復邊：（ 413221 vvvvvv 1 G 為歐拉圖， 1 G 的一條歐拉回路為且 11 GC 1232563542412 vvvvvvvvvvvvC ：對路線 ），），（，重復邊：（ 3242 vvvv 1 v 2 v 3 v 4 v 5 v 6 v 11 1 1 1 1 1 1 1 2 G 為歐拉圖， 2 G 的一條歐拉回路為且 22 GC 歐拉圖一條投遞路線對應一個 條歐拉回路且投遞路線為該圖的一 第17頁/共38頁 反之，對郵路圖G， 的一條鏈到任取奇點 34 vv 3654 ,vv

13、vv如： 對該鏈上的每一條邊增加一條重復邊 G 為歐拉圖 G 存在歐拉回路即G, CG 對應一條投遞路線即 1 v 2 v 3 v 4 v 5 v 6 v 11 1 1 1 1 1 1 1 G 1 v 2 v 3 v 4 v 5 v 6 v 11 1 1 1 1 1 1 1 投遞路線歐拉圖 1454256536321 vvvvvvvvvvvvvC： 第18頁/共38頁 結論：對任意一個含奇點的郵路圖G，由于奇點的個 數為偶數個，把每兩個配成一對，由于G為連 通圖，每對奇點之間至少存在一條鏈，對該 條鏈上的每一條邊增加一條重復邊，可得一 歐拉圖，該歐拉圖對應一條投遞路線 尋找最佳投遞路線方法：

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

15、2v1v6v7v8v9v4 取v6到v8的一條鏈：v6v1v2v3v4v9v8 )( 1為郵局 v G 1 v 2 v 3 v 6 v 4 v 5 v 2 4 3 4 6 9 5 7 v 8 v 9 v 4 4 35 4 第20頁/共38頁 G1 顯然G1不是最佳方案 G1是歐拉圖， 第二步：調整可行方案， 使重復邊權和下降 重復邊權和= 若圖中某條邊有兩條或多于兩條的重復邊 同時去掉偶數條， G2 使圖中每一條邊最多有一條重復邊 G2的重復邊權和= 1 v 2 v 3 v 6 v 4 v 5 v 2 4 3 4 6 9 5 7 v 8 v 9 v 4 4 35 步驟1、 可得到重復邊權和較小

16、的歐拉圖 4 G2 1 v 2 v 3 v 6 v 4 v 5 v 2 4 3 4 6 9 5 7 v 8 v 9 v 4 4 35 4 51 21 第21頁/共38頁 1 v 2 v 3 v 6 v 4 v 5 v 2 4 3 4 6 9 5 7 v 8 v 9 v 4 4 35 G2是歐拉圖， 重復邊權和=21 G2 4 2、使圖中每個初等圈重復邊的 權和不大于該圈權和的一半 9個初等 圈 1 v 2 v 3 v 6 v 4 v 5 v 2 4 3 4 6 9 5 7 v 8 v 9 v 4 4 35 G2 4 G3 G3是歐拉圖， 重復邊權和=17 第22頁/共38頁 G3 1 v 2

17、v 3 v 6 v 4 v 5 v 2 4 3 4 6 9 5 7 v 8 v 9 v 4 4 35 4 6（1）v1v2v5v6v11 6 7 （2）v6v5v8v7v6 14 10 （3）v2v3v4v5v2 24 4 （4）v5v4v9v8v5 16 G3的初等圈權和重復邊權和 13 （5）v1v2v5v8v7v6v124 G4 1 v 2 v 3 v 6 v 4 v 5 v 2 4 3 4 6 9 5 7 v 8 v 9 v 4 4 35 4 第23頁/共38頁 G4 2 v 3 v 6 v 4 v 5 v 2 4 3 4 6 9 5 7 v 8 v 9 v 4 4 35 4 7（1）

18、v1v2v5v6v11 6 4 （2）v6v5v8v7v6 14 4 （3）v2v3v4v5v2 24 8（4）v5v4v9v8v516 G4的初等圈權和重復邊權和 11 （5）v1v2v5v8v7v6v124 1 v （6）v2v3v4v9v8v5v232 4 （8）v6v5v4v9v8v7v6 （7）v1v2v3v4v5v6v128 11 22 4 （9）v1v2v3v4v9v8v7v6v136 7 G4是最佳方案 最佳投遞路線： 16785894561254321 vvvvvvvvvvvvvvvvv 第24頁/共38頁 奇偶點圖上作業法： 第一步：確定一個初始可行方案 方法：檢查圖G中是否有奇點。 無奇點：，找出一條以v0為起點的 歐拉回路，該回路就是最佳投遞路線 有奇點： 圖G已是歐拉圖 把所有奇點兩兩配成一對，每對奇點找一條 鏈，在該條鏈上的每一條邊增加一條重復邊 第二步：調整可行方案，使重復邊權和下降 1、使圖中每一條邊最多有一條重復邊 若圖中某條邊有兩條或多于兩條的重復邊， 同時去掉偶數條 2、使圖中每個初等圈重復邊的權和該圈權和的一半 若圖中某初等圈重復邊的權和大于該圈權和的一半 去掉圈中的重復邊同時將圈中沒有重復邊的邊加上重復邊 第25頁/共38頁 為郵