中國(guó)郵路問題及其算法大學(xué)論文

目錄1引言............................................................................................................................................12中國(guó)郵路問題......................................................................................................................12.1圖的概念.................................................................................................................................12.2道路與回路.............................................................................................................................22.2.1基本概念..........................................................................................................................22.2.2歐拉回路..........................................................................................................................32.3中國(guó)郵路問題.........................................................................................................................32.3.1無向圖的中國(guó)郵路問題..................................................................................................42.3.2有向圖的中國(guó)郵路問題..................................................................................................63中國(guó)郵路問題的算法......................................................................................................83.1無向圖的中國(guó)郵路問題的算法.............................................................................................83.1.1奇偶點(diǎn)圖上作業(yè)法..........................................................................................................83.1.2最小權(quán)匹配算法............................................................................................................103.1.3破圈法............................................................................................................................123.2有向圖的中國(guó)郵路問題的算法...........................................................................................144中國(guó)郵路問題在實(shí)際生活中的應(yīng)用與推廣.....................................................154.1無向圖的中國(guó)郵路問題在實(shí)際生活中的應(yīng)用...................................................................154.2有向圖的中國(guó)郵路問題在實(shí)際生活中的應(yīng)用...................................................................215結(jié)束語....................................................................................................................................23參考文獻(xiàn)...................................................................................................................................24致謝..............................................................................................................................................25i中國(guó)郵路問題及其算法Xxxxxx系本xxxxx班 xxxxxx指導(dǎo)教師：xxxxxxx摘 要：本文利用圖論中的相關(guān)概念闡述并解決中國(guó)郵路問題， 通過比較不同路徑，歸納總結(jié)，找到其具體算法，再利用上述方法找到的具體算法，求解實(shí)例，加以驗(yàn)證，然后將其推廣到實(shí)際生活中，幫助人們快速找到歐拉回路，即找到省時(shí)，省力，省錢的最佳路線，對(duì)于圖論教學(xué)及理論研究均有一定的指導(dǎo)意義。關(guān)鍵詞：中國(guó)郵路，歐拉回路，最佳路線。China'spostalproblemanditsalgorithmXxxxxxxxxClassxxxxx,TheDepartmentofmathematicsInstructor:xxxxxxAbstract:inthispaper,usingtherelevantconceptsinthispaper,thegraphtheoryandsolvetheproblemofChinapostroad,throughcomparingthedifferentpaths,sumup,finditsspecificalgorithm,usingtheabovetofindthespecificalgorithm,solvingtheinstance,verified,andthentopromoteittoreallife,tohelppeoplequicklyfindeularloop,namelyfindtosavetime,effort,savemoney,thebestwayofthegraphtheoryteachingandtheoreticalresearchhavecertainguidingsignificance.Keywords:Chinapostroad,eularcircuit,thebestroute.ii引言中國(guó)郵路問題是我國(guó)著名圖論學(xué)者管梅谷教授首先提出并解決的。 它起初為了幫助郵遞員選擇一條合適道路， 使其在完成任務(wù)的同時(shí)所走路程最短， 后來其方法在實(shí)際生產(chǎn)生活中有廣泛的應(yīng)用，如郵政部門，掃雪車線路，灑水車路線，警車巡邏路線等，具有很強(qiáng)的實(shí)用價(jià)值，本文緊抓其實(shí)質(zhì)與核心，通過對(duì)傳統(tǒng)中國(guó)郵路問題研究方法的歸納總結(jié)，幫助人們快速找出歐拉回路，實(shí)現(xiàn)了將數(shù)學(xué)知識(shí)應(yīng)用于實(shí)際生活中，服務(wù)于人類。中國(guó)郵路問題2.1圖的概念定義1 二元組VG,EG 稱為圖，其中VG是非空集合，稱為結(jié)點(diǎn)集，EG是VG諸結(jié)點(diǎn)之間邊的集合，常用 G V,E表示圖。圖可分為有限圖與無限圖兩類，現(xiàn)只討論V,E都是有限集，給定某個(gè)圖GV,E，如果不加特別說明，認(rèn)為Vv1,v2,v3vn，Ee1,e2,e3em，即結(jié)點(diǎn)數(shù)Vn，邊數(shù)Em。圖G的邊可以是有方向的，也可以是無方向的，它們分別稱為有向邊和無向邊，用ekvi,vj表示。定義2 G V,E的某結(jié)點(diǎn)v所關(guān)聯(lián)的邊數(shù)稱為該結(jié)點(diǎn)的度，用 dv表示。定義3 任意兩結(jié)點(diǎn)間最多只有一條邊，且不存在自環(huán)的無向圖稱為簡(jiǎn)單圖。性質(zhì)1 設(shè)G V,E有n個(gè)結(jié)點(diǎn)，m條邊，則 dv 2m。vVG性質(zhì)2 G中度為奇數(shù)的結(jié)點(diǎn)必為偶數(shù)個(gè)。定義4 若圖G V,E的每條邊ek vi,vj都賦以一個(gè)實(shí)數(shù)wk作為該邊的權(quán)，則稱G是賦權(quán)圖，特別地，如果這些權(quán)都是正實(shí)數(shù)，就稱 G是正權(quán)圖，權(quán)可以表示該邊的長(zhǎng)度，時(shí)間，費(fèi)用或容量等，如下圖 2.1所示：1v234.2v16v353247v4v5圖2.12.2道路與回路2.2.1基本概念定義1有向圖GV,E中，若邊序列Pei1,ei2,ei3eiq，其中eikvi,vj，滿足vi是eik1的終點(diǎn),vj是eik1的始點(diǎn)，就稱P是G的一條有向道路，如果eiq的終點(diǎn)是ei1的始點(diǎn)，則稱P是G的一條有向回路。如果P中的邊沒有重復(fù)出現(xiàn)，則分別稱為簡(jiǎn)單有向道路和簡(jiǎn)單有向回路，進(jìn)而，如果P中結(jié)點(diǎn)也不重復(fù)出現(xiàn)，又分別稱它們?yōu)槌跫?jí)有向道路或初級(jí)有向回路，簡(jiǎn)稱為路或回路。顯然，初級(jí)有向道路（回路）一定是簡(jiǎn)單有向道路（回路）。如下圖2.2.1(a)所示：1e1e5v2e3e4v4e6e2e73圖2.2.1(a)邊序列e5,e4,e5,e7是有向道路；邊序列 e5,e4,e5,e7,e3是有向回路；邊序列e5,e4,e1,e2是簡(jiǎn)單有向道路；邊序列 e5,e4,e1,e2,e3是簡(jiǎn)單有向回路；2邊序列 e1,e2是初級(jí)有向道路；邊序列 e1,e2,e3是初級(jí)有向回路。定義2 無向圖G V,E中，若點(diǎn)邊交替序列 P vi1,ei1,vi2,ei2 eiq1,viq滿足vik,vik1是eik的兩個(gè)端點(diǎn)，則稱 P是G中的一條鏈或道路；如果 viq vi1,則稱P是G中的一個(gè)圈或回路。如下圖 2.2.1(b) 所示：v1e5e1v2 e4e3v4e2e6v3圖2.2.1(b)邊序列e4,e5,e4,e6是道路；邊序列e4,e5,e4,e6,e3是回路；邊序列e4,e5,e1,e2是簡(jiǎn)單道路；邊序列e4,e5,e1,e2,e3是簡(jiǎn)單回路；邊序列e1,e2是初級(jí)道路；邊序列e1,e2,e3是初級(jí)回路。定義3設(shè)G是無向圖，若G的任意兩結(jié)點(diǎn)之間都存在道路，則稱G是連通圖，否則稱為非連通圖。2.2.2歐拉回路定義1對(duì)于連通的無向圖G，若存在一簡(jiǎn)單回路，它通過G的所有邊，則這回路稱為G的Euler回路。定理1 無向連通圖G存在歐拉回路的充要條件是 G中各結(jié)點(diǎn)的度都是偶數(shù)。推論1 若無向連通圖G中只有2個(gè)度為奇數(shù)的結(jié)點(diǎn)，則 G存在歐拉道路。推論2 若有向連通圖G中各結(jié)點(diǎn)的正、負(fù)度相等，則G存在有向歐拉回路。2.3中國(guó)郵路問題中國(guó)郵路問題，它是由中國(guó)數(shù)學(xué)家管梅谷教授首先提出而得名。 設(shè)郵遞員從3郵局出發(fā)，遍歷他所管轄的每一條街道，將信件送到后返回郵局，要求所走的路徑最短，當(dāng)然如若他所管轄的街道構(gòu)成一歐拉回路，則這歐拉回路便是所求的路徑，如若不然，即存在度數(shù)為奇數(shù)的頂點(diǎn)時(shí)，必然有些街道需要走多于1遍，如何尋求最短的路？（基本思路：根據(jù)歐拉圈原理，用奇偶點(diǎn)圖上作業(yè)法，使郵遞路線為最短）現(xiàn)將中國(guó)郵路問題用圖論的語言描述如下：設(shè)G V,E是連通圖，而且對(duì)于所有的 e E,都賦以權(quán)ce 0，求以點(diǎn)v V出發(fā)，通過所有邊至少一次，最后返回 v點(diǎn)的回路C，使得 ce達(dá)到最eC小。2.3.1無向圖的中國(guó)郵路問題郵遞員從郵局出發(fā)，走完投遞線路后又回到郵局，這就要求郵遞員的行走路徑必須是歐拉圈，但是由于城市街道及郵遞點(diǎn)組成的圖有三種基本類型，相應(yīng)的就有三種類型線路，不管何種類型，歸根到底，都要設(shè)法使之形成歐拉圈。圖G里沒有奇次定點(diǎn)。即G中各結(jié)點(diǎn)的度都是偶數(shù)，那么G一定有歐拉回路，顯然任何一條歐拉回路都是該問題的解。如下圖 2.3.1(a)所示：J KA I H GB C D E圖2.3.1(a)投遞路線為： A B C I J K H G E D H I A或者可為：A I H G E D H K J I C B A這時(shí)沒有重復(fù)行走的街道，當(dāng)然郵路最短。圖G中只有2個(gè)結(jié)點(diǎn)vi,vj的度是奇數(shù)，則一定存在從vi到vj的一條歐拉道路，它經(jīng)過了G的各邊一次。在G中再找一條從vj到vi的最短道路pji，則G G pji中存在歐拉回路。這樣 G中的歐拉回路，即對(duì)應(yīng)于 G中pji的邊重復(fù)4一次而其余邊只過一次的回路是一條中國(guó)郵路，即最佳郵路。如下圖 2.3.1(b)所示：F3E21A123D12B2C圖2.3.1（b）如圖，B，E是奇次頂點(diǎn)，因此要構(gòu)成一個(gè)歐拉回路，BE線路必須重復(fù)走一次，這樣存在許多重復(fù)走的方案，例如B F E;B F C E;B C D E;B C E等。我們計(jì)算一下重復(fù)走的長(zhǎng)度分別為 4，6，5，5；當(dāng)然需要重復(fù)走的線路以B F E為最好，故巧加邊，是使其形成歐拉回路的方法，故此時(shí)線路為A B F E D C E F C B F A.總長(zhǎng)度為21，且此路線是最短的。圖G中度為奇數(shù)的結(jié)點(diǎn)數(shù)多于2個(gè)，則需要添加很多條邊，才能形成歐拉回路，且有幾對(duì)奇次頂點(diǎn)，就要加幾條邊，此時(shí)巧加邊問題更加重要。如下圖2.3.1(c)：K5J2G3F21E44H33LI5412A4B3C3D圖2.3.1(c)如圖，有8個(gè)奇次頂點(diǎn)，它們是B,C,E,H,G,J,I,L.如何巧妙地把這8個(gè)奇次頂點(diǎn)恰當(dāng)?shù)亟M合成4對(duì)呢？我們參照上一題的例子，便可將8個(gè)奇次頂點(diǎn)配成以5下4對(duì)：LI,BC,JG,HE.這是必須重復(fù)走的最短線路，且長(zhǎng)度為 11，最優(yōu)投遞路線總長(zhǎng)為60，其中一條最佳路線為A B C D E F G H E H C B I J G J KL I L A2.3.2有向圖的中國(guó)郵路問題圖G中含有正度或負(fù)度為0的結(jié)點(diǎn)，此時(shí)不存在最佳郵路。如圖2.3.2(a)所示：ACB圖2.3.2(a)圖G中各結(jié)點(diǎn)的正，負(fù)度相等，此時(shí)G中一定存在有向歐拉回路。它過每邊一次且僅一次，因此任意一條歐拉回路都是中國(guó)郵路。如下圖 2.3.2(b)所示：A H GB FC D E圖2.3.2(b)(3) 圖G不對(duì)稱，即存在一些結(jié)點(diǎn) vi，d vi d vi，其中d v 的值是以v為始點(diǎn)的邊的數(shù)目， d v的值是以v為終點(diǎn)的邊的數(shù)目。不妨設(shè) d vi d vi，由于郵遞員要經(jīng)過進(jìn)入 vi的每條邊，因此他一定要重復(fù)走以vi為始點(diǎn)的某條邊。設(shè) fij表示邊vi,vj的重復(fù)次數(shù)，wij表示該邊的權(quán)，那么中國(guó)郵路要選擇重復(fù)一些邊后存在有向歐拉回路，并且使 wijfij為最小i,j EG6的一個(gè)解，顯然此時(shí)滿足 d vi fji d vi fij，vi VGj j即 fij fji d vi d vi di.j(i)若di 0，表示郵路中vi要di次重復(fù)經(jīng)過vi所發(fā)出的一些邊，或者說vi可供應(yīng)di個(gè)單位量。(ii)若di 0,表示郵路中vi要di次重復(fù)經(jīng)過進(jìn)入vi的一些邊，或者說 vi可接收di個(gè)單位量。( iii)若di 0,則稱vi是中間結(jié)點(diǎn)。由于 d vi d vi，所以di 0，這樣可以逐次保證每個(gè)可供應(yīng)點(diǎn) vi經(jīng)過一些邊向某個(gè)接收點(diǎn) vj供應(yīng)一個(gè)單位量，最后達(dá)到平衡，或者說這些道路上的邊出現(xiàn)重復(fù)，最后得到的圖G是有向歐拉圖，若這些重復(fù)邊的總長(zhǎng)最小，它即是最佳郵路。例1 求下圖的中國(guó)郵路。28725v33v1v55124解此題顯然是有向中國(guó)郵路問題中的不對(duì)稱型，故(1)各結(jié)點(diǎn)的di為d1d50，d22，d31，d41。(2)構(gòu)造G如下圖2.3.2(c):70vsv2v208275v33vv3v15v1v55012v40vtv4圖2.3.2(c)圖2.3.2(d)(3)得到2條總和最小的st道路P1vs,v2,v4,vt,P15；PP2vs,v2,v4,v3,vt，P26;故Pi11.這樣邊v2,v4重復(fù)2次，邊v4,v3重復(fù)1次，得圖2.3.2(d)，其中虛線邊表示重復(fù)1次。圖2.3.2(d)是歐拉圖，其中一條歐拉回路，如v1,v2,v4,v3,v2,v4,v3,v5,v2,v4,v5,v1就是最佳郵路。中國(guó)郵路問題的算法3.1無向圖的中國(guó)郵路問題的算法3.1.1奇偶點(diǎn)圖上作業(yè)法把G中所有奇度數(shù)頂點(diǎn)配成對(duì)，將每對(duì)奇度數(shù)頂點(diǎn)之間的一條路上的每邊改為二重邊，得到一個(gè)新圖G1,新圖G1中沒有奇度數(shù)頂點(diǎn)，即G1為多重Euler圖。若G1中某一對(duì)頂點(diǎn)之間有多于2條邊連接，則去掉其中的偶數(shù)條邊，留下1條或2條邊連接這兩個(gè)頂點(diǎn)，直到每一對(duì)相鄰頂點(diǎn)至多由2條邊連接，得到圖G2。檢查G2的每一個(gè)圈C,若某一個(gè)圈C上重復(fù)邊的權(quán)和超過此圈權(quán)和的一半，則將C進(jìn)行調(diào)整。重復(fù)這一過程，直到對(duì)G2的所有圈，其重復(fù)邊的權(quán)和不超過此圈權(quán)和的一半，得到圖G3。求G3的Euler回路。8例2 求下圖所示圖G的中國(guó)郵路。v12v104v95v85364v2646v7v11v125447v39v43v58v6圖G解圖G中有6個(gè)奇度數(shù)頂點(diǎn)v2,v4,v5,v7,v9,v10.把它們配成三對(duì)：v2與v5,v4與v7,v9與v10，在圖G中，取一條v2與v5的路v2v3v4v5，把邊v2,v3,v3,v4,v4,v5作為重復(fù)邊加入圖中；再取v4與v7之間一條路v4v5v6v7，把邊v4,v5,v5,v6,v6,v7作為重復(fù)邊加入圖中，在v9和v10之間加一條重復(fù)邊v9,v10，如圖(2)，這個(gè)圈沒有奇度數(shù)點(diǎn)，是一個(gè)Euler圖。v12v104v95v8v12v104v95v853645364v2646v2646v7v11v7v11v12v1254475447938938v3v4v5v6v3v4vv65(2)(3)在圖(2)中，頂點(diǎn)v4與v5之間有三條重邊，去掉其中兩條，得到圖 (3)，該圖仍是一個(gè)Euler圖。在圖(3)中，圈v2v3v4v11v2的總權(quán)為24，而圈上重復(fù)邊的權(quán)和為 14，大于該圈總權(quán)的一半，于是去掉邊 v2,v3和v3,v4上的重復(fù)邊，而在v2,v11和v4,v11上加入重復(fù)邊，此時(shí)重復(fù)邊的權(quán)和為 10，小于該圈總權(quán)的一半。同理，圈v5v6v7v12v59的總權(quán)和為15，去掉邊 v5,v6和v6,v7上的重復(fù)邊，在邊 v5,v12和v7,v12上加重復(fù)邊，如下圖(4)：v12v104v95v8v12v104v95v853645364v26v11v126v7v26v114v126v7454475447v39v43v58v6v39v43v58v6(4)(5)圖(4)中，圈v4v5v12v11v4的總權(quán)為15，而重復(fù)邊的權(quán)和為 8，從而調(diào)整為圖(5)。圖(5)中,圈v1v2v11v12v7v8v9v10v1的總權(quán)為36,而重復(fù)邊的總權(quán)為20,繼續(xù)調(diào)整為圖(6)：v1 v10 v9 v8v11v12v7v2v3 v4 v5 v66）經(jīng)檢驗(yàn)，圖(6)為最優(yōu)方案，其中一條歐拉回路就是最佳郵路。3.1.2最小權(quán)匹配算法確定G中度為奇數(shù)的結(jié)點(diǎn)，構(gòu)成V0G。(2)求V0G各結(jié)點(diǎn)在G中的最短路徑Pij及其長(zhǎng)度vi,vj。(3)對(duì)V0G的結(jié)點(diǎn)進(jìn)行最小權(quán)匹配，即選出V0G/2個(gè)vi,vj,保證每個(gè)結(jié)點(diǎn)viV0G在Pij中只出現(xiàn)一次，同時(shí)滿足這些vi,vj的總和最小。(4)在最小權(quán)匹配里各vi,vj所對(duì)應(yīng)的路徑Pij中的諸邊在G中重復(fù)一次，得10到G。G是歐拉圖，它的一條歐拉回路即為最優(yōu)解。例3求下圖所示圖G的中國(guó)郵路。v25v31223v1v72v43453v63v5解顯然此題屬于無向圖的中國(guó)郵路問題，故(1)首先找到奇數(shù)結(jié)點(diǎn)，V0Gv2,v3,v4,v5,v6,v7。(2)求V0G各結(jié)點(diǎn)在G中的最短路徑Pij及長(zhǎng)度vi,vj，P23v2,v7,v3，234；P24v2,v7,v4，244；P25v2,v7,v5，257；P26v2,v1,v6，264；P27v2,v7，272；P34v3,v4，343；P35v3,v4,v5，356；P36v3,v7,v6，366；P37v3,v7，372；P45v4,v5，453；P46v4,v5,v6，466；P47v4,v7，472；P56v5,v6，563；P57v5,v7，575；P67v6,v7，674.(3)對(duì)V0G的結(jié)點(diǎn)進(jìn)行最小權(quán)匹配，得最佳匹配v2,v7,v3,v4,v5,v6。(4)在最小權(quán)匹配里各vi,vj所對(duì)應(yīng)的路徑Pij中的諸邊在G中重復(fù)一次，得到下圖G。11v25v31223v1v72v43453v63v5G是歐拉圖，故它的一條歐拉回路即為最優(yōu)解。3.1.3破圈法奇點(diǎn)處作出標(biāo)記如加“*”或“o”;求該圖的最小樹（用破圈法，盡可能多的保留與奇點(diǎn)相連的邊）；在最小樹上的奇點(diǎn)處添加重復(fù)邊，以消滅奇點(diǎn)；回到原問題，且按判優(yōu)準(zhǔn)則檢驗(yàn)與調(diào)整，直至最優(yōu)。注1最小生成樹的求法：設(shè)G是連通加權(quán)簡(jiǎn)單圖，若G不是樹，則G中必有回路，我們刪去G中含于某回路內(nèi)權(quán)最大的一條邊，所得圖記為G1，G1是G的連通生成子圖，下一步，若 G1不是樹，又從G1的某回路內(nèi)刪去權(quán)最大的一條邊，如此下去，最后不能按上述方法刪邊時(shí)，得到的圖 T便是G的一棵生成樹，即T是G的最小生成樹。例4求下面圖中的最優(yōu)郵路。A2H4G533B6I4F544C9D4E解 顯然此題屬于無向圖的中國(guó)郵路問題，故(1)先在圖中找到奇點(diǎn)，并記上“ o”，如圖(1)：12A2H4G533B6I4F544C9D4E（1）求出該圖最小樹，如圖(2)：A 2 H G533BI4F544CDE（2）在最小樹上添加重復(fù)邊，以消滅奇點(diǎn)，如圖(3)：A2HG533BI4F544CDE(3)(4)經(jīng)檢驗(yàn)，此已是最優(yōu)解。A2H4G533B6I4F544C9D4E13此題的一條最優(yōu)路線為CDIFEDIHGFIBAHABC3.2有向圖的中國(guó)郵路問題的算法對(duì)稱有向圖的中國(guó)郵路算法較為簡(jiǎn)單，下面只研究非對(duì)稱有向圖的中國(guó)郵路算法，算法如下：(1)計(jì)算各結(jié)點(diǎn)的正，負(fù)度，求出di，且didvidvi。(2)添加一個(gè)超發(fā)點(diǎn)vs，對(duì)滿足di0的結(jié)點(diǎn)vi，加入di條有向邊vs,vi，權(quán)均為0；添加一個(gè)超收點(diǎn)vt，對(duì)滿足dj0的結(jié)點(diǎn)vj，加入dj條有向邊vj,vt，權(quán)均為0，得到圖G。(3)在G中求dvs條過以vs，vt為兩端點(diǎn)的形如vs,vi，vj,vt每邊一次且僅一次的總和最小的 Pst道路，記下G中各邊在這些道路中的重復(fù)次數(shù)。計(jì)入各邊的重復(fù)次數(shù)，G中存在有向歐拉回路，其中一條即為解。例5求下圖的中國(guó)郵路。v123v52v25123v41v3解 顯然此題屬于非對(duì)稱有向圖的中國(guó)郵路問題，故(1)先求各結(jié)點(diǎn)的di為d12，d21，d31，(2)構(gòu)造G如下圖(a)：14vs0v103v522v250123vtv41v30(a)(3)得到2條總和最小的st道路P1vs,v1,v3,vt,P12；PP2vs,v1,v3,v2,vt,P24;Pi6.這樣邊v1,v3重復(fù)2次，邊v3,v2重復(fù)1次，得下圖，其中虛線邊表示重復(fù)1次。v13v522v251 23v4 1 v3(4)上圖即為歐拉圖，其中一條歐拉回路如 v1,v3,v2,v1,v3,v2,v4,v1,v3,v4,v5,v1就是最佳郵路。中國(guó)郵路問題在實(shí)際生活中的應(yīng)用與推廣4.1無向圖的中國(guó)郵路問題在實(shí)際生活中的應(yīng)用例6如下圖(1)所示是忻州師范學(xué)院主區(qū)俯視圖，圖(2)是校內(nèi)主干道的簡(jiǎn)略圖，其中每條道路上至少有一個(gè)垃圾筒，收垃圾大叔每天需將校內(nèi)所有的垃圾倒掉，下圖中各邊上的數(shù)字表示在此條路上完成任務(wù)所需時(shí)間（單位為分鐘），問如何設(shè)計(jì)路線才能使大叔在完成任務(wù)的同時(shí)，所用時(shí)間最短？15v12 2 v11 2 v104 4 4v8v9v72222v6v41v52332v2v322v1(1)(2)分析我們把這個(gè)問題抽象成上圖(2)所示，其中G的結(jié)點(diǎn)vi表示幾條相交道路的交點(diǎn)，各道路可用交點(diǎn)間的邊表示，于是此問題就等價(jià)于圖 G中是否存在經(jīng)過圖G的每邊一次且僅一次的閉跡問題。方法一 用奇偶點(diǎn)圖上作業(yè)法解 在G中有6個(gè)奇度數(shù)頂點(diǎn)v2,v3,v5,v4,v9,v11.把它們配成三對(duì):v2與v4,v3與v5,v9與v11.在G中，取一條連接v2與v4的路v2v3v4，并把邊v2,v3，v3,v4作為重復(fù)邊加入圖中；再將v3與v5間一條路v3v4v5，把邊v3,v4，v4,v5作為重復(fù)邊加入圖中，在v9與v11之間加一條重復(fù)邊v9,v11，如下圖(a)中，這個(gè)圖中沒有奇度數(shù)點(diǎn)，是一個(gè)Euler圖。16v12 2 v11 2 v10 v12 2 v11 2 v10444444v7v8v9v7v8v922222222v62v62v41v5v41v53333v22v3v22v32222v1v1(a)(b)在圖(a)中，頂點(diǎn)v3，v4間有三條重邊，去掉其中兩條，得到圖(b)，該圖仍是一個(gè)Euler圖。在圖(b)中，圈v1,v2,v3,v1的總權(quán)為6，而重復(fù)邊的權(quán)和為2，小于該圈總權(quán)的一半；圈v2,v3,v4,v5,v6,v2的總權(quán)為11，而重復(fù)邊的權(quán)和為4，小于該圈總權(quán)的一半；圈v5,v4,v9,v8,v5的總權(quán)為8，而重復(fù)邊的權(quán)和為2，小于該圈總權(quán)的一半；圈v8,v9,v10,v11,v8的總權(quán)為12，而重復(fù)邊的權(quán)和為6，等于該圈總權(quán)的一半；圈v5,v4,v9,v10,v11,v8,v5的總權(quán)為16，而重復(fù)邊的權(quán)和為8，等于該圈總權(quán)的一半；圈v7,v8,v9,v10,v11,v12,v7的總權(quán)為20，而重復(fù)邊的權(quán)和為6，小于該圈總權(quán)的一半。由此看來，在每個(gè)圈上，都滿足重復(fù)邊的權(quán)和不超過此圈權(quán)和的一半，故圖(b)為最優(yōu)方案，其中一條歐拉回路即為最佳郵路，如v1,v2,v6,v5,v8,v7,v12,v11,v8,v9,v10,v11,v10,v9,v4,v5,v4,v3,v2,v3,v1即為一條最優(yōu)郵路，且最短時(shí)間為 49。17方法二最小權(quán)匹配算法解顯然此題屬于無向圖的中國(guó)郵路問題，故(1)先找出奇數(shù)結(jié)點(diǎn)V0Gv2,v3,v4,v5,v9,v11；(2)再求V0G各結(jié)點(diǎn)在G中的最短路徑Pij及長(zhǎng)度vi,vj，P23v2,v3，232；P24v2,v3,v4，245；P25v2,v6,v5，254；P29v2,v3,v4,v9，297；P2,11v2,v6,v5,v8,v11，2,1110；P34v3,v4，343；P35v3,v4,v5，355；P39v3,v4,v9，395；P3,11v3,v4,v9,v10,v11，3,1111；P45v4,v5，452；P49v4,v9，492；P4,11v4,v9,v10,v11，4,118；P59v5,v4,v9，594；P5,11v5,v8,v11，5,116；P9,11v9,v10,v11，9,116。對(duì)V0G的結(jié)點(diǎn)進(jìn)行最小權(quán)匹配，得最佳匹配為v2與v3,v4與v5,v9與v11,在最小權(quán)匹配里各vi,vj所對(duì)應(yīng)的路徑Pij中的諸邊在G中重復(fù)一次，得到上圖，且其為歐拉圖，故它的一條歐拉回路即為最優(yōu)郵路。方法三 用破圈法來求解此題解 顯然此題屬于無向圖的中國(guó)郵路問題，故先在圖中找出奇點(diǎn)，并記上“o”,如下圖(a)：求出該圖最小樹，如下圖(b)：18v12 2 v11 2 v10 v12 2 v11 2 v104 4 4 4v8v9v8v9v7v72222222v62v621v5v41v5v433322v2v3v2v3222v1v1(a)(b)在最小樹上添加重復(fù)邊，以消滅奇點(diǎn),如圖(c)：v12 2 v11 2 v104v8v9v7222v621v5v432v2 v32v1(c)19經(jīng)檢驗(yàn)，此解已是最優(yōu)解，其中任意一條歐拉回路即為最優(yōu)解，如v1,v2,v6,v5,v8,v7,v12,v11,v8,v9,v10,v11,v10,v9,v4,v5,v4,v3,v2,v3,v1即為解，且最短時(shí)間為49。例7下圖是忻州師院校內(nèi)某超市的內(nèi)部過道，剛剛開學(xué)時(shí)，某同學(xué)需要購(gòu)買的物品比較多，下圖中的數(shù)字表示在此貨架上尋找自己所需物品的時(shí)間（單位為分鐘），問若他能一次性購(gòu)齊所有物品，如何規(guī)劃路線能使其所用時(shí)間最短？v8v7v6v5v42312541261223v9v10v1v2v3分析 本題用上述的三種方法均可求解，下面用破圈法為例解決此題。解(1)先找到圖中的奇點(diǎn)，并記上“o”，如圖(a)所示：v8v7v6v5v42312541261223v9v10v1v2v3(a)求出該圖的最小樹，如圖(b)所示：（方法用破圈法）v8 v7 v6 v5 v42 3 1 21 2123v9v10v1v2v3(b)20在最小樹上添加重復(fù)邊，以消滅奇點(diǎn),如圖(c)：v8v7v6v5v423125 4 1 2 61223v9v10v1v2v3(c)經(jīng)檢驗(yàn)，此解已是最優(yōu)解，如v1,v2,v3,v4,v5,v2,v1,v6,v7,v8,v9,v10,v1,v6,v7,v10,v1 就是一條最優(yōu)中國(guó)郵路，且最短用時(shí)為41。4.2有向圖的中國(guó)郵路問題在實(shí)際生活中的應(yīng)用例8實(shí)例圖仍為忻州師范學(xué)院，校內(nèi)由于道路較窄，每到開學(xué)季，進(jìn)入校內(nèi)的車輛較多，故每條道路都為單行線，其方向如圖所示，某家長(zhǎng)想開車環(huán)游整個(gè)校園，問如何規(guī)劃路線才能使其在不違反規(guī)定的條件下，將校內(nèi)每條道的風(fēng)景都領(lǐng)略到呢？v12 2 v11 2 v104 4 4v8v9v72222v6v41v52332v2 v32 2v121解 顯然此題屬于非對(duì)稱有向圖的中國(guó)郵路問題，故(1)求得各結(jié)點(diǎn)的di為d1d6d7d10d120，d3d4d