中國郵路問題及其算法

1、目目 錄錄1 1 引引言言.12 2 中國郵路問題中國郵路問題.12.1 圖的概念圖的概念.12.2 道路與回路道路與回路.22.2.1 基本概念基本概念.22.2.2 歐拉回路歐拉回路.32.3 中國郵路問題中國郵路問題.32.3.1 無向圖的中國郵路問無向圖的中國郵路問題題.42.3.2 有向圖有向圖的的中國郵路問題中國郵路問題.63 3 中國郵路問題的算法中國郵路問題的算法.83.1 無向圖的中無向圖的中國國郵路問題的算法郵路問題的算法.83.1.1 奇偶點圖上作業(yè)法奇偶點圖上作業(yè)法.83.1.2 最小權(quán)匹配算法最小權(quán)匹配算法.103.1.3 破圈法破圈法.123.2 有向圖的中國郵路問

2、題的算法有向圖的中國郵路問題的算法.144 4 中國郵路問題在實際生活中的應(yīng)用與推廣中國郵路問題在實際生活中的應(yīng)用與推廣.154.1 無向圖的中國郵路問題在實際生活中的無向圖的中國郵路問題在實際生活中的應(yīng)應(yīng)用用.154.2 有向圖的中國郵路問題在實際生活中的應(yīng)用有向圖的中國郵路問題在實際生活中的應(yīng)用.215 5 結(jié)束語結(jié)束語.23參考文獻參考文獻.24致謝致謝.25i中國郵路問題及其算法XxxxxxXxxxxx 系本系本 xxxxxxxxxx 班班 xxxxxxxxxxxx指導(dǎo)教師：指導(dǎo)教師： xxxxxxxxxxxxxx 摘 要：本文利用圖論中的相關(guān)概念闡述并解決中國郵路問題，通過比較不同路

3、徑，歸納總結(jié)，找到其具體算法，再利用上述方法找到的具體算法，求解實例，加以驗證，然后將其推廣到實際生活中，幫助人們快速找到歐拉回路，即找到省時，省力，省錢的最佳路線，對于圖論教學及理論研究均有一定的指導(dǎo)意義。關(guān)鍵詞：中國郵路，歐拉回路，最佳路線。Chinas postal problem and its algorithmXxxxxxxxxXxxxxxxxxClass xxxxx,The Department of mathematicsInstructor: xxxxxx Abstract: in this paper, using the relevant concepts in this

4、 paper, the graph theory and solve the problem of China post road, through comparing the different paths, sum up, find its specific algorithm, using the above to find the specific algorithm, solving the instance, verified, and then to promote it to real life, to help people quickly find eular loop,

5、namely find to save time, effort, save money, the best way of the graph theory teaching and theoretical research have certain guiding significance. Key words: China post road, eular circuit, the best route. 01 引言 中國郵路問題是我國著名圖論學者管梅谷教授首先提出并解決的。它起初為了幫助郵遞員選擇一條合適道路，使其在完成任務(wù)的同時所走路程最短，后來其方法在實際生產(chǎn)生活中有廣泛的應(yīng)用，如郵

6、政部門，掃雪車線路，灑水車路線，警車巡邏路線等，具有很強的實用價值，本文緊抓其實質(zhì)與核心，通過對傳統(tǒng)中國郵路問題研究方法的歸納總結(jié)，幫助人們快速找出歐拉回路，實現(xiàn)了將數(shù)學知識應(yīng)用于實際生活中，服務(wù)于人類。2 中國郵路問題2.1 圖的概念圖的概念定義 1 二元組稱為圖，其中是非空集合，稱為結(jié)點集， GEGV, GV是諸結(jié)點之間邊的集合，常用表示圖。 GE GVEVG,(1) 圖可分為有限圖與無限圖兩類，現(xiàn)只討論,都是有限集，給定某VE個圖，如果不加特別說明，認為，EVG,nvvvvV321,，即結(jié)點數(shù)，邊數(shù)。meeeeE321,nV mE (2) 圖的邊可以是有方向的，也可以是無方向的，它們分別

7、稱為有向邊G和無向邊，用表示。jikvve,定義 2 的某結(jié)點v所關(guān)聯(lián)的邊數(shù)稱為該結(jié)點的度，用表示。EVG, vd定義 3 任意兩結(jié)點間最多只有一條邊，且不存在自環(huán)的無向圖稱為簡單圖。性質(zhì) 1 設(shè)有個結(jié)點，條邊，則。EVG,nm mvdGVv2性質(zhì) 2 中度為奇數(shù)的結(jié)點必為偶數(shù)個。G定義 4 若圖的每條邊都賦以一個實數(shù)作為該邊的EVG,jikvve,kw權(quán)，則稱是賦權(quán)圖，特別地，如果這些權(quán)都是正實數(shù)，就稱是正權(quán)圖，權(quán)GG可以表示該邊的長度，時間，費用或容量等，如下圖 2.1 所示： 134734.2562v2v1v5v4v3圖 2.12.2 道路與回路道路與回路2.2.1 基本概念基本概念定義

8、 1 有向圖中，若邊序列，其中EVG,iqiiieeeeP321,，滿足是的終點,是的始點，就稱是的一條有向道jiikvve,iv1ikejv1ikePG路，如果的終點是的始點，則稱是的一條有向回路。iqe1 iePG如果中的邊沒有重復(fù)出現(xiàn)，則分別稱為簡單有向道路和簡單有向回路，P進而，如果中結(jié)點也不重復(fù)出現(xiàn)，又分別稱它們?yōu)槌跫売邢虻缆坊虺跫売邢騊回路，簡稱為路或回路。顯然，初級有向道路（回路）一定是簡單有向道路（回路） 。如下圖 2.2.1(a)所示：e7e6e5e4e3e1e2v1v3v2v4圖 2.2.1(a)邊序列是有向道路；邊序列是有向回路；7545,eeee37545,eeeee邊

9、序列是簡單有向道路；邊序列是簡單有向回路；2145,eeee32145,eeeee2邊序列是初級有向道路；邊序列是初級有向回路。21,ee321,eee定義 2 無向圖中，若點邊交替序列滿EVG,iqiqiiiiveevevP,12211足,是的兩個端點，則稱是中的一條鏈或道路；如果,則ikv1ikvikePG1 iiqvv稱是中的一個圈或回路。如下圖 2.2.1(b)所示：PGe5e4e3e1e2e6v1v3v2v4圖 2.2.1(b)邊序列是道路；邊序列是回路；6454,eeee36454,eeeee邊序列是簡單道路；邊序列是簡單回路；2154,eeee32154,eeeee邊序列是初級道

10、路；邊序列是初級回路。21,ee321,eee定義 3 設(shè)是無向圖，若的任意兩結(jié)點之間都存在道路，則稱是連GGG通圖，否則稱為非連通圖。2.2.2 歐拉回路歐拉回路定義 1 對于連通的無向圖，若存在一簡單回路，它通過的所有邊，GG則這回路稱為的 Euler 回路。G定理 1 無向連通圖存在歐拉回路的充要條件是中各結(jié)點的度都是偶GG數(shù)。推論 1 若無向連通圖中只有 2 個度為奇數(shù)的結(jié)點，則存在歐拉道路。GG推論 2 若有向連通圖中各結(jié)點的正、負度相等，則存在有向歐拉回GG路。32.3 中國郵路問題中國郵路問題 中國郵路問題，它是由中國數(shù)學家管梅谷教授首先提出而得名。設(shè)郵遞員從郵局出發(fā)，遍歷他所管

11、轄的每一條街道，將信件送到后返回郵局，要求所走的路徑最短，當然如若他所管轄的街道構(gòu)成一歐拉回路，則這歐拉回路便是所求的路徑，如若不然，即存在度數(shù)為奇數(shù)的頂點時，必然有些街道需要走多于1 遍，如何尋求最短的路？（基本思路：根據(jù)歐拉圈原理，用奇偶點圖上作業(yè)法，使郵遞路線為最短）現(xiàn)將中國郵路問題用圖論的語言描述如下：設(shè)是連通圖，而且對于所有的,都賦以權(quán)，求以點EVG,Ee 0ec出發(fā)，通過所有邊至少一次，最后返回 點的回路，使得達到最VvvC Ceec小。2.3.1 無向圖的中國郵路問題無向圖的中國郵路問題郵遞員從郵局出發(fā)，走完投遞線路后又回到郵局，這就要求郵遞員的行走路徑必須是歐拉圈，但是由于城市

12、街道及郵遞點組成的圖有三種基本類型，相應(yīng)的就有三種類型線路，不管何種類型，歸根到底，都要設(shè)法使之形成歐拉圈。(1)圖里沒有奇次定點。即中各結(jié)點的度都是偶數(shù)，那么一定有歐GGG拉回路，顯然任何一條歐拉回路都是該問題的解。如下圖 2.3.1(a)所示：HIJKCAGDBE圖 2.3.1(a)投遞路線為：AIHDEGHKJICBA或者可為：ABCIJKHDEGHIA這時沒有重復(fù)行走的街道，當然郵路最短。(2)圖中只有 2 個結(jié)點,的度是奇數(shù)，則一定存在從到的一條歐Givjvivjv4拉道路，它經(jīng)過了的各邊一次。在中再找一條從到的最短道路，則GGjvivjip中存在歐拉回路。這樣中的歐拉回路，即對應(yīng)于

13、中的邊重jipGGGGjip復(fù)一次而其余邊只過一次的回路是一條中國郵路，即最佳郵路。如下圖 2.3.1(b)所示：312321221FEBCDA圖 2.3.1（b）如圖，是奇次頂點，因此要構(gòu)成一個歐拉回路，線路必須重復(fù)走BEEB 一次，這樣存在許多重復(fù)走的方案，例如;EFBECFB;等。EDCBECB我們計算一下重復(fù)走的長度分別為 4，6，5，5；當然需要重復(fù)走的線路以為最好，故巧加邊，是使其形成歐拉回路的方法，故此時線路為EFB.總長度為 21，且此路AFBCFECDEFBA線是最短的。(3)圖中度為奇數(shù)的結(jié)點數(shù)多于 2 個，則需要添加很多條邊，才能形成歐G拉回路，且有幾對奇次頂點，就要加幾

14、條邊，此時巧加邊問題更加重要。如下圖 2.3.1(c)：5234333314254214KJGFDABCLIHE5圖 2.3.1(c)如圖，有 8 個奇次頂點，它們是,.如何巧妙地把這 8 個奇BCEHGJIL次頂點恰當?shù)亟M合成 4 對呢？我們參照上一題的例子，便可將 8 個奇次頂點配成以下 4 對：,.這是必須重復(fù)走的最短線路，且長度為 11，最LIBCJGHE優(yōu)投遞路線總長為 60，其中一條最佳路線為ALILKJGJIBCHEHGFEDCBA2.3.2 有向圖的中國郵路問題有向圖的中國郵路問題(1) 圖中含有正度或負度為 0 的結(jié)點，此時不存在最佳郵路。如圖G2.3.2(a)所示：ABC圖

15、 2.3.2(a)(2) 圖中各結(jié)點的正，負度相等，此時中一定存在有向歐拉回路。它GG過每邊一次且僅一次，因此任意一條歐拉回路都是中國郵路。如下圖 2.3.2(b)所示：AHGFEBCD圖 2.3.2(b)(3) 圖不對稱，即存在一些結(jié)點，其中 的值是Giv iivdvd vd以 為始點的邊的數(shù)目，的值是以 為終點的邊的數(shù)目。v vdv不妨設(shè)，由于郵遞員要經(jīng)過進入的每條邊，因此他一定 iivdvdiv6要重復(fù)走以為始點的某條邊。設(shè)表示邊的重復(fù)次數(shù)，表示該邊的ivijfjivv ,ijw權(quán)，那么中國郵路要選擇重復(fù)一些邊后存在有向歐拉回路，并且使為 GEjiijijfw,最小的一個解，顯然此時滿足

16、， jijijjiifvdfvd GVvi即. idvdvdffiijjiij(i)若，表示郵路中要次重復(fù)經(jīng)過所發(fā)出的一些邊，或者說0 idividiv可供應(yīng)個單位量。ivid(ii)若,表示郵路中要次重復(fù)經(jīng)過進入的一些邊，或者說0 idividiv可接收個單位量。ivid (iii)若,則稱是中間結(jié)點。由于，所以0 idiv iivdvd，這樣可以逐次保證每個可供應(yīng)點經(jīng)過一些邊向某個接收點供0idivjv應(yīng)一個單位量，最后達到平衡，或者說這些道路上的邊出現(xiàn)重復(fù)，最后得到的圖是有向歐拉圖，若這些重復(fù)邊的總長最小，它即是最佳郵路。G例 1 求下圖的中國郵路。55218372v2v3v4v1v5解

17、 此題顯然是有向中國郵路問題中的不對稱型，故(1)各結(jié)點的為，。id 051dd 22 d 13d 14d(2)構(gòu)造如下圖 2.3.2(c):G7000055218372v2v3v4v1v5vsvt v2v3v4v5v1 圖 2.3.2(c) 圖 2.3.2(d)(3)得到 2 條總和最小的道路,；stPtsvvvvP,421 51P，;故.這樣邊重復(fù) 2 次，邊tsvvvvvP,3422 62P 11iP42,vv重復(fù) 1 次，得圖 2.3.2(d)，其中虛線邊表示重復(fù) 1 次。34,vv(4)圖 2.3.2(d)是歐拉圖，其中一條歐拉回路，如就是最佳郵路。154253423421,vvvv

18、vvvvvvvv3 中國郵路問題的算法3.1 無向圖的中國郵路問題的算法無向圖的中國郵路問題的算法3.1.1 奇偶點圖上作業(yè)法奇偶點圖上作業(yè)法(1)把中所有奇度數(shù)頂點配成對，將每對奇度數(shù)頂點之間的一條路上的每G邊改為二重邊，得到一個新圖,新圖中沒有奇度數(shù)頂點，即為多重 Euler1G1G1G圖。 (2)若中某一對頂點之間有多于 2 條邊連接，則去掉其中的偶數(shù)條邊，1G留下 1 條或 2 條邊連接這兩個頂點，直到每一對相鄰頂點至多由 2 條邊連接，得到圖。2G (3)檢查的每一個圈,若某一個圈上重復(fù)邊的權(quán)和超過此圈權(quán)和的一2GCC半，則將進行調(diào)整。重復(fù)這一過程，直到對的所有圈，其重復(fù)邊的權(quán)和不C

19、2G超過此圈權(quán)和的一半，得到圖。3G8 (4)求的 Euler 回路。3G例 2 求下圖所示圖的中國郵路。G24555938346464647v12v11v1v10v9v8v2v3v4v5v6v7圖 G解 圖中有 6 個奇度數(shù)頂點,.把它們配成三對：G2v4v5v7v9v10v與,與,與，在圖中，取一條與的路，把邊,2v5v4v7v9v10vG2v5v5432vvvv32,vv,作為重復(fù)邊加入圖中；再取與之間一條路，把邊43,vv54,vv4v7v7654vvvv,作為重復(fù)邊加入圖中，在和之間加一條重復(fù)邊54,vv65,vv76,vv9v10v，如圖(2)，這個圈沒有奇度數(shù)點，是一個 Eule

20、r 圖。109,vv24555938346464647v12v11v1v10v9v8v2v3v4v5v6v7 24555938346464647v12v11v1v10v9v8v2v3v4v5v6v7(2) (3)在圖(2)中，頂點與之間有三條重邊，去掉其中兩條，得到圖(3)，該4v5v圖仍是一個 Euler 圖。在圖(3)中，圈的總權(quán)為 24，而圈上重復(fù)邊的權(quán)和為 14，大于該211432vvvvv圈總權(quán)的一半，于是去掉邊和上的重復(fù)邊，而在和32,vv43,vv112,vv9上加入重復(fù)邊，此時重復(fù)邊的權(quán)和為 10，小于該圈總權(quán)的一半。同理，114,vv圈的總權(quán)和為 15，去掉邊和上的重復(fù)邊，在

21、邊和512765vvvvv65,vv76,vv125,vv上加重復(fù)邊，如下圖(4)：127,vv24555938346464647v12v11v1v10v9v8v2v3v4v5v6v7 24555938346464647v12v11v1v10v9v8v2v3v4v5v6v7(4) (5)圖(4)中，圈的總權(quán)為 15，而重復(fù)邊的權(quán)和為 8，從而調(diào)整為圖4111254vvvvv(5)。圖(5)中,圈的總權(quán)為 36,而重復(fù)邊的總權(quán)為 20,繼續(xù)調(diào)整110987121121vvvvvvvvv為圖(6)：v11v1v8v2v7v4v5v6v3v10v12v9（6）經(jīng)檢驗，圖(6)為最優(yōu)方案，其中一條歐拉

22、回路就是最佳郵路。3.1.2 最小權(quán)匹配算法最小權(quán)匹配算法(1)確定中度為奇數(shù)的結(jié)點，構(gòu)成。G GV0(2)求各結(jié)點在中的最短路徑及其長度。 GV0GijPjivv ,(3)對的結(jié)點進行最小權(quán)匹配，即選出個,保證每個 GV0 2/0GVjivv ,10結(jié)點在中只出現(xiàn)一次，同時滿足這些的總和最小。 GVvi0ijPjivv ,(4)在最小權(quán)匹配里各所對應(yīng)的路徑中的諸邊在中重復(fù)一次，jivv ,ijPG得到。G(5)是歐拉圖，它的一條歐拉回路即為最優(yōu)解。G例 3 求下圖所示圖的中國郵路。G52432331325v2v3v5v6v4v1v7解 顯然此題屬于無向圖的中國郵路問題，故(1)首先找到奇數(shù)結(jié)

23、點，。 7654320,vvvvvvGV(2)求各結(jié)點在中的最短路徑及長度， GV0GijPjivv ,，； ，；37223,vvvP42347224,vvvP 424，； ，；57225,vvvP 72561226,vvvP 426，； ，；7227,vvP 2274334,vvP 334，； ，；54335,vvvP 63567336,vvvP 636，； ，；7337,vvP 2375445,vvP 345，； ，；65446,vvvP 6467447,vvP 247，； ，；6556,vvP 3567557,vvP 557，.7667,vvP 467(3)對的結(jié)點進行最小權(quán)匹配，得最佳

24、匹配,。 GV072,vv43,vv65,vv(4)在最小權(quán)匹配里各所對應(yīng)的路徑中的諸邊在中重復(fù)一次，jivv ,ijPG得到下圖。G1152432331325v2v3v5v6v4v1v7(5)是歐拉圖，故它的一條歐拉回路即為最優(yōu)解。G3.1.3 破圈法破圈法(1)奇點處作出標記如加“*”或“o”;(2)求該圖的最小樹（用破圈法，盡可能多的保留與奇點相連的邊） ；(3)在最小樹上的奇點處添加重復(fù)邊，以消滅奇點； (4)回到原問題，且按判優(yōu)準則檢驗與調(diào)整，直至最優(yōu)。注 1 最小生成樹的求法：設(shè)是連通加權(quán)簡單圖，若不是樹，則中GGG必有回路，我們刪去中含于某回路內(nèi)權(quán)最大的一條邊，所得圖記為，是G1

25、G1G的連通生成子圖，下一步，若不是樹，又從的某回路內(nèi)刪去權(quán)最大的一G1G1G條邊，如此下去，最后不能按上述方法刪邊時，得到的圖便是的一棵生成TG樹，即是的最小生成樹。TG例 4 求下面圖中的最優(yōu)郵路。243434449655AHGFEIDCB解 顯然此題屬于無向圖的中國郵路問題，故(1)先在圖中找到奇點，并記上“o” ，如圖(1)：12243434449655AHGFEIDCB（1）(2)求出該圖最小樹，如圖(2)：23434455AHGFEIDCB（2）(3)在最小樹上添加重復(fù)邊，以消滅奇點，如圖(3)：23434455AHGFEIDCB(3)(4)經(jīng)檢驗，此已是最優(yōu)解。243434449

26、655AHGFEIDCB13此題的一條最優(yōu)路線為CBAHABIFGHIDEFIDC3.2 有向圖的中國郵路問題的算法有向圖的中國郵路問題的算法對稱有向圖的中國郵路算法較為簡單，下面只研究非對稱有向圖的中國郵路算法，算法如下：(1)計算各結(jié)點的正，負度，求出，且。id iivdvdid(2)添加一個超發(fā)點，對滿足的結(jié)點，加入條有向邊sv0 idivid，權(quán)均為 0；添加一個超收點，對滿足的結(jié)點，加入isvv ,tv 0 jdjv條有向邊，權(quán)均為 0，得到圖。 jdtjvv ,G(3)在中求條過以，為兩端點的形如，每邊一次且G svdsvtvisvv ,tjvv ,僅一次的總和最小的道路，記下中各

27、邊在這些道路中的重復(fù)次數(shù)。stPG(4)計入各邊的重復(fù)次數(shù)，中存在有向歐拉回路，其中一條即為解。G例 5 求下圖的中國郵路。15221323v4v3v1v5v2解 顯然此題屬于非對稱有向圖的中國郵路問題，故(1)先求各結(jié)點的為，id21 d 12d 13d(2)構(gòu)造如下圖(a)：G14000015221323v4v3v1v5v2vsvt(a)(3)得到 2 條總和最小的道路,；stPtsvvvvP,311 21P,;.這樣邊重復(fù) 2 次，邊重tsvvvvvP,2312 42P 6iP31,vv23,vv復(fù) 1 次，得下圖，其中虛線邊表示重復(fù) 1 次。15221323v4v3v1v5v2(4)上

28、圖即為歐拉圖，其中一條歐拉回路如 就是最佳郵路。154314231231,vvvvvvvvvvvv4 中國郵路問題在實際生活中的應(yīng)用與推廣4.1 無向圖的中國郵路問題在實際生活中的應(yīng)用無向圖的中國郵路問題在實際生活中的應(yīng)用例 6 如下圖(1)所示是忻州師范學院主區(qū)俯視圖，圖(2)是校內(nèi)主干道的簡略圖，其中每條道路上至少有一個垃圾筒，收垃圾大叔每天需將校內(nèi)所有的垃圾倒掉，下圖中各邊上的數(shù)字表示在此條路上完成任務(wù)所需時間（單位為分鐘） ，問如何設(shè)計路線才能使大叔在完成任務(wù)的同時，所用時間最短？15 2244422222132322v12v11v10v9v8v7v5v4v6v2v3v1 (1) (2

29、)分析 我們把這個問題抽象成上圖(2)所示，其中的結(jié)點表示幾條相交Giv道路的交點，各道路可用交點間的邊表示，于是此問題就等價于圖中是否存G在經(jīng)過圖的每邊一次且僅一次的閉跡問題。G方法一 用奇偶點圖上作業(yè)法解 在中有 6 個奇度數(shù)頂點,.把它們配成三對:與G2v3v5v4v9v11v2v,與,與.在中，取一條連接與的路，并把邊，4v3v5v9v11vG2v4v432vvv32,vv作為重復(fù)邊加入圖中；再將與間一條路，把邊，43,vv3v5v543vvv43,vv作為重復(fù)邊加入圖中，在與之間加一條重復(fù)邊，如下圖(a)54,vv9v11v119,vv中，這個圖中沒有奇度數(shù)點，是一個 Euler 圖

30、。162244422222132322v12v11v10v9v8v7v5v4v6v2v3v1 2244422222132322v12v11v10v9v8v7v5v4v6v2v3v1 (a) (b)在圖(a)中，頂點，間有三條重邊，去掉其中兩條，得到圖(b)，該圖3v4v仍是一個 Euler 圖。在圖(b)中，圈的總權(quán)為 6，而重復(fù)邊的權(quán)和為 2，小于該圈總1321,vvvv權(quán)的一半；圈的總權(quán)為 11，而重復(fù)邊的權(quán)和為 4，小于該圈265432,vvvvvv總權(quán)的一半；圈的總權(quán)為 8，而重復(fù)邊的權(quán)和為 2，小于該圈總58945,vvvvv權(quán)的一半；圈的總權(quán)為 12，而重復(fù)邊的權(quán)和為 6，等于該圈

31、總8111098,vvvvv權(quán)的一半；圈的總權(quán)為 16，而重復(fù)邊的權(quán)和為 8，等于該581110945,vvvvvvv圈總權(quán)的一半；圈的總權(quán)為 20，而重復(fù)邊的權(quán)和為 6，小7121110987,vvvvvvv于該圈總權(quán)的一半。由此看來，在每個圈上，都滿足重復(fù)邊的權(quán)和不超過此圈權(quán)和的一半，故圖(b)為最優(yōu)方案，其中一條歐拉回路即為最佳郵路，如即為一條最優(yōu)郵路，13234549101110981112785621,vvvvvvvvvvvvvvvvvvvvv且最短時間為 49。17方法二 最小權(quán)匹配算法解 顯然此題屬于無向圖的中國郵路問題，故(1)先找出奇數(shù)結(jié)點； 11954320,vvvvvvG

32、V (2)再求各結(jié)點在中的最短路徑及長度， GV0GijPjivv , ， ； ，；3223,vvP 22343224,vvvP 524 ，； ，；56225,vvvP 425943229,vvvvP 729 ，；11856211, 2,vvvvvP1011, 2 ，； ，；4334,vvP 33454335,vvvP 535 ，； ，；94339,vvvP 539111094311, 3,vvvvvP1111, 3，； ，；5445,vvP 2459449,vvP 249，；11109411, 4,vvvvP811, 4，； ，；94559,vvvP 459118511, 5,vvvP611

33、, 5，。1110911, 9,vvvP611, 9對的結(jié)點進行最小權(quán)匹配，得最佳匹配為與,與,與,在 GV02v3v4v5v9v11v最小權(quán)匹配里各所對應(yīng)的路徑中的諸邊在中重復(fù)一次，得到上圖jivv ,ijPG(b)，且其為歐拉圖，故它的一條歐拉回路即為最優(yōu)郵路。方法三 用破圈法來求解此題解 顯然此題屬于無向圖的中國郵路問題，故(1)先在圖中找出奇點，并記上“o”,如下圖(a)：(2)求出該圖最小樹，如下圖(b)：182244422222132322v12v11v10v9v8v7v5v4v6v2v3v1 22422221232v12v11v10v9v8v7v5v4v6v2v3v1 (a) (

34、b) (3)在最小樹上添加重復(fù)邊，以消滅奇點,如圖(c)：22422221232v12v11v10v9v8v7v5v4v6v2v3v1 (c)19(4)經(jīng)檢驗，此解已是最優(yōu)解，其中任意一條歐拉回路即為最優(yōu)解，如 即為解，且最短時13234549101110981112785621,vvvvvvvvvvvvvvvvvvvvv間為 49。例 7 下圖是忻州師院校內(nèi)某超市的內(nèi)部過道，剛剛開學時，某同學需要購買的物品比較多，下圖中的數(shù)字表示在此貨架上尋找自己所需物品的時間（單位為分鐘） ，問若他能一次性購齊所有物品，如何規(guī)劃路線能使其所用時間最短？2312513641222v8v7v6v5v4v9v1

35、0v2v3v1分析 本題用上述的三種方法均可求解，下面用破圈法為例解決此題。解 (1)先找到圖中的奇點，并記上“o” ，如圖(a)所示：2312513641222v8v7v6v5v4v9v10v2v3v1(a)(2)求出該圖的最小樹，如圖(b)所示：（方法用破圈法）231213122v8v7v6v5v4v9v10v2v3v120(b)(3)在最小樹上添加重復(fù)邊，以消滅奇點,如圖(c)：2312513641222v8v7v6v5v4v9v10v2v3v1(c)(4)經(jīng)檢驗，此解已是最優(yōu)解，如 就是一條最優(yōu)中國郵路，且最1107611098761254321,vvvvvvvvvvvvvvvvv短用

36、時為 41。4.2 有向圖的中國郵路問題在實際生活中的應(yīng)用有向圖的中國郵路問題在實際生活中的應(yīng)用 例 8 實例圖仍為忻州師范學院，校內(nèi)由于道路較窄，每到開學季，進入校內(nèi)的車輛較多，故每條道路都為單行線，其方向如圖所示，某家長想開車環(huán)游整個校園，問如何規(guī)劃路線才能使其在不違反規(guī)定的條件下，將校內(nèi)每條道的風景都領(lǐng)略到呢？212244422222132322v12v11v10v9v8v7v5v4v6v2v3v1解 顯然此題屬于非對稱有向圖的中國郵路問題，故(1)求得各結(jié)點的為， id 01210761ddddd，。 111943dddd 152dd 28 d(2)構(gòu)造如圖(b)：G22000000002244422222132322v12v11v10v9v8v7v5v4v6v2v3v1vsvt(b)(3)得到 4 條總和最小的道路,;stPtsvvvvvP,3121 41P,;,tsvvvvvvvvP,4312