第十九章 行遍性問(wèn)題

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

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

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

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

支上及其分枝上的點(diǎn)分在同一組;準(zhǔn)則二：應(yīng)將相鄰的干枝上的點(diǎn)分在同一組;)支上及其分枝上的點(diǎn)分在同一組;準(zhǔn)則二：應(yīng)將相鄰的干枝上的點(diǎn)分在同一組;),10_.0\43.227z.A/o28、22is\(7.9\12.1\/82311>7.9\/9.2113^1-clZ8準(zhǔn)則三：盡量將長(zhǎng)的干枝與短的干枝分在同一組.由上述分組準(zhǔn)則，們找到兩種分組形式如下分組一：（⑥，①），（②，③），（⑤，④）分組二：（①，②），（③，④），（⑤，⑥）顯然分組一的方法極不均衡，故考慮分組二.對(duì)分組二中每組頂點(diǎn)的生成子圖，用算法一求出近似最優(yōu)解及相應(yīng)的巡視路線(xiàn).在每個(gè)子圖所構(gòu)造的完備圖中，取一個(gè)盡量包含圖中樹(shù)上的邊的H圈作為其第2步輸入的初始圈.分組二的近似解見(jiàn)表1表1小組名稱(chēng)路線(xiàn)總路線(xiàn)長(zhǎng)度路線(xiàn)的總長(zhǎng)度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因?yàn)樵摲纸M的均衡度①（C）—①（C）241.9-125.5

氣=Mhx^（C）=241.9ii=1,2,3所以此分法的均衡性很差.為改善均衡性，將第II組中的頂點(diǎn)C,2,3,D,4劃歸第III組，重新分組后的近似最優(yōu)解見(jiàn)表2.小組名稱(chēng)路線(xiàn)總路線(xiàn)長(zhǎng)度路線(xiàn)的總長(zhǎng)度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因?yàn)樵摲纸M的均衡度①（C）-①（C）216.4—191.1a=%-『1==11.69%0Max?（c）216.4ii=1,2,3所以這種分法的均衡性較好.問(wèn)題二當(dāng)巡視人員在各鄉(xiāng)鎮(zhèn)、村的停留時(shí)問(wèn)一定，汽車(chē)的行駛速度一定，要在24小時(shí)內(nèi)完成巡視，至少要分幾組及最佳的巡視路線(xiàn).由于T=2小時(shí)，t=1小時(shí)，V=35公里/小時(shí)，需訪(fǎng)問(wèn)的鄉(xiāng)鎮(zhèn)共有了17個(gè)，村共有35個(gè).計(jì)算出在鄉(xiāng)鎮(zhèn)及村的總停留時(shí)間為17x2+35=69小時(shí)，要在24小時(shí)內(nèi)完成巡回，若不考慮行走時(shí)間，故至少要分4組.由于該網(wǎng)絡(luò)的鄉(xiāng)鎮(zhèn)、村分布較為均勻，故有可能找出停留時(shí)問(wèn)盡量均衡的分組，當(dāng)分4組時(shí)各組停留時(shí)間大約為岑=17.25小時(shí)，則每組分配在路途上的時(shí)問(wèn)大約為24-17.25=6.75小時(shí)而前面討論過(guò)，分三組時(shí)有個(gè)總路程59