第十九章 行遍性問題

第十九章行遍性問題、中國郵遞員問題定義1設(shè)G=(V,E)是連通無向圖經(jīng)過G的每邊至少一次的閉通路稱為巡回.經(jīng)過G的每邊正好一次的巡回稱為歐拉巡回.存在歐拉巡回的圖稱為歐拉圖.歐拉道路:vevevevevev11223514433歐拉巡回：vevevevevevev1122351443361歐拉道路:vevevevevev11223514433巡回：vevevevevevev1122351443351定理1對于非空連通圖G,下列命題等價:G是歐拉圖.G無奇次頂點.G的邊集能劃分為圈.

非歐拉圖非歐拉圖推論1設(shè)G是非平凡連通圖，則G有歐拉道路的充要條件是G最多只有兩個奇次頂點.19.1.2.中國郵遞員問題郵遞員發(fā)送郵件時，要從郵局出發(fā)，經(jīng)過他投遞范圍內(nèi)的每條街道至少一次，然后返回郵局，但郵遞員希望選擇一條行程最短的路線.這就是中國郵遞員問題.若將投遞區(qū)的街道用邊表示，街道的長度用邊權(quán)表示，郵局街道交叉口用點表示，則一個投遞區(qū)構(gòu)成一個賦權(quán)連通無向圖.中國郵遞員問題轉(zhuǎn)化為：在一個非負加權(quán)連通圖中，尋求一個權(quán)最小的巡回.這樣的巡回稱為最佳巡回.G是歐拉圖此時G的任何一個歐拉巡回便是最佳巡回.問題歸結(jié)為在歐拉圖中確定一個歐拉巡回.Fleury算法便解決了這一問題.Fleury算法的基本思想：從任一點出發(fā)，每當訪問一條邊時，先要進行檢查.如果可供訪問的邊不只一條，則應(yīng)選一條不是未訪問的邊集的導出子圖的割邊作為訪問邊，直到?jīng)]有邊可選擇為止.注：割邊的定義：設(shè)G聯(lián)通，egE(G)，若從G中刪除邊e后，圖G-{e}不聯(lián)通，則稱邊e為圖G的割邊.Fleury算法：求歐拉圖的歐拉巡回：任選一個頂點y0，令道路氣=V。.假定道路w=veve…ev已經(jīng)選好，則從E\{e,e,…,e}中選一條邊e，、/I/、-—I?]]2?,'，-~1~、-//V/°,/JI，、-、，'-.|]/使：匕+i與七相關(guān)聯(lián)除非不能選擇，否則一定要使?！覆皇荊=G[E-{e,e,…,e}]的割邊.i+1i12i(3)第(2)步不能進行時就停止.G不是歐拉圖若G不是歐拉圖，則G的任何一個巡回經(jīng)過某些邊必定多于一次.解決這類問題的一般方法是，在一些點對之間引入重復邊(重復邊與它平行的邊具有相同的權(quán))，使原圖成為歐拉圖，但希望所有添加的重復邊的權(quán)的總和為最小.情形1G正好有兩個奇次頂點設(shè)G正好有兩個奇次頂點u和v,求G的最佳巡回如下：用Dijkstra算法求出奇次頂點u與v之間的最短路徑P令G*=GuP，則G*為歐拉圖用Fleury算法求出G*的歐拉巡回，這就是G的最佳巡回.情形2G有2n個奇次頂點(n>2)Edmonds最小對集算法：基本思想：先將奇次頂點配對，要求最佳配對，即點對之間距離總和最小.再沿點對之間的最短路徑添加重復邊得歐拉圖G*，G*的歐拉巡回便是原圖的最佳巡回.算法步驟：用Floyd算法求出的所有奇次頂點之間的最短路徑和距離.以G的所有奇次頂點為頂點集(個數(shù)為偶數(shù))，作一完備圖，邊上的權(quán)為兩端點在原圖G中的最短距離，將此完備加權(quán)圖記為G1.求出G1的最小權(quán)理想匹配M，得到奇次頂點的最佳配對.在G中沿配對頂點之間的最短路徑添加重復邊得歐拉圖G*.用Fleury算法求出G*的歐拉巡回，這就是G的最佳巡回.例求圖19-1所示投遞區(qū)的一條最佳郵遞路線.V610V3圖19-1

解圖中有v4、v7、v8、v9四個奇次頂點，用Floyd算法求出它們之間的最短路徑和距離：P=VVVV,d(v,v)=5V/7432747P=VV,d(v,v)=3V4V84848P=VVV,d(vv)=6V4V94894,9P=VV,d(v,v)=9V7V87878P=VV,d(v,v)=6V7V97979P=VV,d(v,v)=3V8V98989以v4、v7、v8、v9為頂點，它們之間的距離為邊權(quán)構(gòu)造完備圖勺，如圖19-2.圖19-3圖圖19-3求出G的最小權(quán)完美匹配M={(v,v),(v,v)}.14,789在G中沿v到匕的最短路徑添加重復邊，沿v到vq的最短路徑vv添加重復邊，得歐4/8989拉圖G2.如圖19-3.G2中一條歐拉巡回就是G的一條最佳巡回.其權(quán)值為64.二、推銷員問題一個旅行售貨員想去訪問若干城鎮(zhèn)，然后回到出發(fā)地.給定各城鎮(zhèn)之間的距離后，應(yīng)怎樣計劃他的旅行路線，使他能對每個城鎮(zhèn)恰好經(jīng)過一次而總距離最??？它可歸結(jié)為這樣的圖論問題：在一個賦權(quán)完全圖中，找出一個最小權(quán)的H圈，稱這種圈為最優(yōu)圈.但這個問題是NP-hard問題，即不存在多項式時間算法也就是說,對于大型網(wǎng)絡(luò)(賦權(quán)圖),目前還沒有一個求解旅行售貨員問題的有效算法，因此只能找一種求出相當好(不一定最優(yōu))的解.1、哈密爾頓圖定義1設(shè)G=(V,E)是連通無向圖經(jīng)過G的每個頂點正好一次的路徑，稱為G的一條哈密爾頓路徑，簡稱H路徑.經(jīng)過G的每個頂點正好一次的圈，稱為G的哈密爾頓圈或H圈.含H圈的圖稱為哈密爾頓圖或H圖.2、推銷員問題-定義流動推銷員需要訪問某地區(qū)的所有城鎮(zhèn)，最后回到出發(fā)點.問如何安排旅行路線使總行程最小.這就是推銷員問題若用頂點表示城鎮(zhèn)，邊表示連接兩城鎮(zhèn)的路，邊上的權(quán)表示距離(或時間、費用)，于是推銷員問題就成為在加權(quán)圖中尋找一條經(jīng)過每個頂點至少一次的最短閉通路問題定義2在加權(quán)圖G=(V,E)中，(1)權(quán)最小的哈密爾頓圈稱為最佳H圈.經(jīng)過每個頂點至少一次的權(quán)最小的閉通路稱為最佳推銷員回路.一般說來，最佳哈密爾頓圈不一定是最佳推銷員回路同樣最佳推銷員回路也不一定是一般說來，最佳哈密爾頓圈不一定是最佳推銷員回路同樣最佳推銷員回路也不一定是最佳哈密爾頓圈.定理1在加權(quán)圖G=(V,E)中，若對任意x,y,zeV，z。x,z。y,都有w(x,y)<w(x,z)+w(z,y),則圖G的最佳H圈也是最佳推銷員回路.最佳推銷員回路問題可轉(zhuǎn)化為最佳H圈問題.方法是由給定的圖G=(V,E)構(gòu)造一個以V為頂點集的完備圖G'=(V,E')，E'的每條邊(x,y)的權(quán)等于頂點x與y在圖中最短路的權(quán).即：Vx,yeE',w(x,y)=min@(x,y)

定理2加權(quán)圖G的最佳推銷員回路的權(quán)與G’的最佳H圈的權(quán)相同.3、推銷員問題近似算法推銷員問題近似算法：二邊逐次修正法任取初始H圈：C=vv...vv12n1對所有的i,j,1<i+1<j<v，若w(vv)+w(vv)<w(vv)+w(vv)iji+1j+1ii+1jj+1則在％中刪去邊vv和vv而加入邊vv和vv，形成新的H圈C,即0ii+1jj+1iji+1j+1C=vv...vvv12ijj+1見圖19-4圖19-4...vvv...vvi+1j+1j+2n見圖19-4圖19-4...vvv...vvi+1j+1j+2n1圖19-5例1解首先任選一初始H圈：C=vvvvvvv01234561見圖19-6（a）.可以看出，w(vv)+wv.珊J去邊vv和vv,加入邊vv,vv,得到一個新451245142w(vv)+C=vvvvvvv11432561而圖19-6(b)中，w(vv)+w(vv)<w(vv)+w(vv),刪去邊vv和vv,加入邊vv,TOC\o"1-5"\h\z15261625162515v2七’得到一個新的H圈C2，見圖19-6(C).而圖(C)中，w(vv)+w(vv)<w(vv)+w(vv)，刪去邊vv和vv，加入邊vv,vv，得到一個1345153415341345新的H圈C,C=vvvvvvv，見圖19-6(d).其權(quán)為W(C)=192.3314562313?⑷圖19-6?⑷為了知道找出的這個解的好壞可用最優(yōu)H圈的權(quán)的下界與其比較而得出.即利用最小生成樹可得最優(yōu)H圈的一個下界，方法如下：設(shè)C是G的一個最優(yōu)H圈，則對G的任一頂點v,C-v是G-v的路，也G-v是的生成樹.如果T是G-v的最小生成樹，且匕是氣與v關(guān)聯(lián)的邊中權(quán)最小的兩條邊，則w(T)+w(e)+w(e2)將是w(C)的一個下界.若取v=v3，得G-v3的一最小生成樹(實線)，(圖19-7)其權(quán)w(T)=122，與v3關(guān)聯(lián)的權(quán)最小的兩條邊為vv和vv,故w(C)=w(T)+w(vv)+w(vv)=178.故最優(yōu)H圈的權(quán)應(yīng)13231323滿足178<w(C)<192.圖19-7三、最佳災情巡視路線1998年全國大學生數(shù)學模型競賽B題中的兩個問題.一、問題今年夏天某縣遭受水災.為考察災情、組織自救，縣領(lǐng)導決定，帶領(lǐng)有關(guān)部門負責人到全縣各鄉(xiāng)（鎮(zhèn)）、村巡視.巡視路線指從縣政府所在地出發(fā)，走遍各鄉(xiāng)（鎮(zhèn)）、村，又回到縣政府所在地的路線.若分三組（路）巡視，試設(shè)計總路程最短且各組盡可能均衡的路線.假定巡視人員在各鄉(xiāng)（鎮(zhèn)）停留時間T=2小時，在各村停留時間t=1小時，汽車行駛速度V=35公里/小時.要在24小時內(nèi)完成巡視，至少應(yīng)分幾組；給出這種分組下最佳的巡視路線.鄉(xiāng)（鎮(zhèn)）、村的公路網(wǎng)示意圖見圖19-8二、基本假設(shè)汽車在路上的速度總是一定，不會出現(xiàn)拋錨等現(xiàn)象；巡視當中，在每個鄉(xiāng)鎮(zhèn)、村的停留時間一定，不會出現(xiàn)特殊情況而延誤時間；每個小組的汽車行駛速度完全一樣；分組后，各小組只能走自己區(qū)內(nèi)的路，不能走其他小組的路，除公共路外.三、模型的建立與分析本問題要求在某縣的鄉(xiāng)鎮(zhèn)、村公路網(wǎng)中，尋找從縣政府所在地圖中點出發(fā)，走遍各鄉(xiāng)鎮(zhèn)、村，又回到縣政府所在地，使總路程或時問最少將公路網(wǎng)圖中，每個鄉(xiāng)鎮(zhèn)或村看為圖中圖19-8的一個節(jié)點，各鄉(xiāng)鎮(zhèn)、村之間的公路看作圖中對應(yīng)節(jié)點間的邊，各條公路的長度或行駛時間看作對應(yīng)邊上的權(quán)，所給公路網(wǎng)就轉(zhuǎn)化為圖論中的加權(quán)網(wǎng)絡(luò)圖，問題就轉(zhuǎn)化為一個圖論問題，即在給定的加權(quán)網(wǎng)絡(luò)圖中尋找從給定點出發(fā)，行遍所有頂點至少一次再回到點，使得總權(quán)路程或時間最小.算法一求加權(quán)圖G(V,E)的最佳推銷員回路的近似算法：1、用圖論軟件包求出G中任意兩個頂點間的最短路，構(gòu)造出完備圖G'(V,E'),V(x,y)eE',?)(x,y)=Mindd(x,y)；G2、輸入圖G'的一個初始H圈；3、用對角線完全算法產(chǎn)生一個初始H圈；4、隨機搜索出G'中若干個H圈，例如2000個；5、對第2、3、4步所得的每個H圈，用二邊逐次修正法進行優(yōu)化，得到近似最佳H圈;6、在第5步求出的所有H圈中，找出權(quán)最小的一個，此即要找的最佳H圈的近似解.由于二邊逐次修正法的結(jié)果與初始圈有關(guān)，故本算法第2、3、4步分別用三種方法產(chǎn)生初始圈，以保證能得到較優(yōu)的計算結(jié)果.問題一若分為三組巡視，設(shè)計總路程最短且各組盡可能均衡的巡視路線.此問題是多個推銷員的最佳推銷員回路問題即在加權(quán)圖G中求頂點集V的劃分，V,V,^V，將g分成n個生成子圖g[y],g\y],???G[y]使得12n12n(1)頂點OeV,i=1,2,,n.i⑵Uy=y(g).ii=1Max從c)—①G)i,7Mv\JR，其中c是y的導出子圖g[v]中的最佳推銷員回Max?(C)iiiii路，?(C)為C的權(quán)，i,J=1,2,…，n.乙(c)=Min.ii=1定義稱Max?(c)—?(c)iJ1氣=—ii為該分組的實際路程均衡度.a為最大容許均衡度.顯然0<a0<1,a0越小，說明分組的均衡性越好.取定一個a后，a0與a滿足條件(3)的分組是一個均衡分組.條件(4)表示總巡視路程最短.此問題包含兩方面：第一、對頂點分組；第二、在每組中求最佳推銷員回路，即為單個推銷員的最佳推銷員問題.我們只能去尋求一種較合理的劃分準則，對圖進行初步劃分后，求出各部分的近似最佳推銷員回路的權(quán)，再進一步進行調(diào)整，使得各部分滿足均衡性條件(3).從O點出發(fā)去其它點，要使路程較小應(yīng)盡量走O點到該點的最短路.故用圖論軟件包求出O點到其余頂點的最短路，這些最短路構(gòu)成一棵O為樹根的樹，將從O點出發(fā)的樹枝稱為干枝，見圖19-9.從圖中可以看出，從O點出發(fā)到其它點共有6條干枝，它們的名稱分別為①，②，③，④，③，⑥.

支上及其分枝上的點分在同一組;準則二：應(yīng)將相鄰的干枝上的點分在同一組;)支上及其分枝上的點分在同一組;準則二：應(yīng)將相鄰的干枝上的點分在同一組;),10_.0\43.227z.A/o28、22is\(7.9\12.1\/82311>7.9\/9.2113^1-clZ8準則三：盡量將長的干枝與短的干枝分在同一組.由上述分組準則，們找到兩種分組形式如下分組一：（⑥，①），（②，③），（⑤，④）分組二：（①，②），（③，④），（⑤，⑥）顯然分組一的方法極不均衡，故考慮分組二.對分組二中每組頂點的生成子圖，用算法一求出近似最優(yōu)解及相應(yīng)的巡視路線.在每個子圖所構(gòu)造的完備圖中，取一個盡量包含圖中樹上的邊的H圈作為其第2步輸入的初始圈.分組二的近似解見表1表1小組名稱路線總路線長度路線的總長度IO-P-28-27-26-N-24-23-22-17-16-I-15-I-18-K-21-20-25-M-O191.1558.5IIO-2-5-6-L-19-J-11-G-13-14-H-12-F-10-F-9-E-8-4-D-3-C241.9mO-R-29-Q-30-32-31-33-35-34-A-B-1-O125.5因為該分組的均衡度①（C）—①（C）241.9-125.5

氣=Mhx^（C）=241.9ii=1,2,3所以此分法的均衡性很差.為改善均衡性，將第II組中的頂點C,2,3,D,4劃歸第III組，重新分組后的近似最優(yōu)解見表2.小組名稱路線總路線長度路線的總長度IO-P-28-27-26-N-24-23-22-17-16-I-15-I-18-K-21-20-25-M-O191.1558.5IIO-2-5-6-7-E-8-E-9-F-10-F-12-H-14-13-G-11-J-19-L-6-5-2-O216.4mO-R-29-Q-30-32-31-33-35-34-A-1-B-3-D-4-D-3-2-O192.3因為該分組的均衡度①（C）-①（C）216.4—191.1a=%-『1==11.69%0Max?（c）216.4ii=1,2,3所以這種分法的均衡性較好.問題二當巡視人員在各鄉(xiāng)鎮(zhèn)、村的停留時問一定，汽車的行駛速度一定，要在24小時內(nèi)完成巡視，至少要分幾組及最佳的巡視路線.由于T=2小時，t=1小時，V=35公里/小時，需訪問的鄉(xiāng)鎮(zhèn)共有了17個，村共有35個.計算出在鄉(xiāng)鎮(zhèn)及村的總停留時間為17x2+35=69小時，要在24小時內(nèi)完成巡回，若不考慮行走時間，故至少要分4組.由于該網(wǎng)絡(luò)的鄉(xiāng)鎮(zhèn)、村分布較為均勻，故有可能找出停留時問盡量均衡的分組，當分4組時各組停留時間大約為岑=17.25小時，則每組分配在路途上的時問大約為24-17.25=6.75小時而前面討論過，分三組時有個總路程59