圖論中幾個典型問題的求解

圖論中幾個典型問題的求解第1頁，共161頁，2023年，2月20日，星期六§1圖的基本概念第2頁，共161頁，2023年，2月20日，星期六圖是一種直觀形象地描述已知信息的方式，它使事物之間的關(guān)系簡潔明了，是分析問題的有用工具，很多實際問題可以用圖來描述。第3頁，共161頁，2023年，2月20日，星期六一、圖的定義

圖論是以圖為研究對象的數(shù)學(xué)分支，在圖論中，圖由一些點和點之間的連線所組成．

稱圖中的點為頂點（節(jié)點），稱連接頂點的沒有方向的線段為邊，稱有方向的線段為?。肰={v1,v2,…}表示全體頂點的集合，用

E={e1,e2,…}表示全體邊的集合，如果對于E中的任一條邊ek，在V中都有一對頂點(vi,vj)和它對應(yīng)，則稱由V和E組成的集體為一個圖，記為G={V,E}，簡寫為G．第4頁，共161頁，2023年，2月20日，星期六二、基本概念

點與邊相連接稱為關(guān)聯(lián)，與邊e關(guān)聯(lián)的頂點稱為該邊的端點，與同一條邊關(guān)聯(lián)的兩個頂點稱為相鄰頂點，與同一個頂點關(guān)聯(lián)的邊稱為相鄰邊．具有相同頂點的邊稱為平行邊，兩個端點重合的邊稱為環(huán)．所有線段都沒有方向的圖稱為無向圖，所有線段都有方向的圖稱為有向圖，既有邊也有弧的圖稱為混合圖．在無向圖中，沒有環(huán)和平行邊的圖稱為簡單圖，任意兩個頂點之間都有一條邊相連的簡單圖稱為完全圖．任意兩個頂點之間有且只有一條弧相連的有向圖稱為競賽圖．第5頁，共161頁，2023年，2月20日，星期六在無向圖中與頂點v關(guān)聯(lián)的邊的數(shù)目（環(huán)算兩次）稱為該頂點的度（或次數(shù)），記為d(v)。度為奇數(shù)的頂點叫做奇點，度為偶數(shù)的頂點叫做偶點。在有向圖中，從頂點v引出的邊的數(shù)目稱為該頂點的出度，記為d+(v)，從頂點v引入的邊的數(shù)目稱為該頂點的入度，記為d-(v)，而d(v)＝d+(v)+d-(v)稱為v的次數(shù)。第6頁，共161頁，2023年，2月20日，星期六在圖中，兩個頂點u和v之間由頂點和邊構(gòu)成的交錯序列（使u和v相通）稱為鏈（通道），沒有重復(fù)邊的通道稱為跡，起點與終點重合的通道稱為閉通道，不重合的稱為開通道，沒有重復(fù)頂點（必然邊也不重復(fù)）的開通道稱為路，起點與終點重合的路稱為圈（回路）．包含奇數(shù)個頂點（或邊）的圈稱為奇圈，包含偶數(shù)個頂點（或邊）的圈稱為偶圈。如果頂點u和v之間存在一條路，則稱u和v是連通的，任意兩個頂點都連通的圖稱為連通圖．無圈的連通圖稱為樹，如果一棵樹T包含了圖G的所有頂點，稱T為G的生成樹．第7頁，共161頁，2023年，2月20日，星期六如果圖G的每條邊e都對應(yīng)一個實數(shù)C(e)，稱C(e)為該邊e的權(quán)，稱圖G為賦權(quán)圖．通常稱賦權(quán)的有向圖為網(wǎng)絡(luò)．圖中邊e6和e7是平行邊，e9是環(huán)，頂點v4是懸掛點，邊e4是懸掛邊．第8頁，共161頁，2023年，2月20日，星期六§2最短路問題第9頁，共161頁，2023年，2月20日，星期六最短路問題是圖論應(yīng)用的基礎(chǔ)，很多實際問題，如線路的布設(shè)、運輸規(guī)劃、運輸網(wǎng)絡(luò)最小費用流等問題，都可以通過建立最短路模型來求解。有些有深度的圖與網(wǎng)絡(luò)優(yōu)化問題，如旅行售貨商、中國郵遞員等問題，需要在首先求出任意兩點之間最短路的基礎(chǔ)上解決。一、最短路的概念給定一個連通的賦權(quán)圖G={V,E}，設(shè)R是連接節(jié)點vi和vj的一條路，該路的權(quán)定義為路中所有各邊權(quán)之和，如果路R在所有連接節(jié)點vi和vj的路中權(quán)最小，則稱它為vi和vj間的最短路。第10頁，共161頁，2023年，2月20日，星期六二、任意兩點之間的最短路(Floyd算法)Floyd算法利用距離矩陣進(jìn)行迭代運算，可以一次性地求出任意兩點之間的最短路，該方法的思路有創(chuàng)意，計算量小，編程較簡單，又稱矩陣求解法。1．算法原理

設(shè)A=[aij]m×n是圖的權(quán)矩陣（也稱帶權(quán)鄰接矩陣），其中aij是圖上連接頂點i和j的邊的權(quán)，如果兩頂點之間沒有直接相連的邊（即兩頂點不相鄰），則aij=∞。第11頁，共161頁，2023年，2月20日，星期六令矩陣D(0)=A，作為迭代的初始矩陣，從它出發(fā)按照一定規(guī)則求D(1)，又由D(1)按照類似的規(guī)則求D(2)，依此類推進(jìn)行迭代直至求出D(n)，設(shè)矩陣D(m)的元素為dij(m)，迭代規(guī)則為：

上式表示dij(1)在dij(0)以及從頂點vi經(jīng)過頂點v1到vj的權(quán)之和di1(0)+d1j(0)兩者之中選擇最短長度。依此規(guī)則迭代。第12頁，共161頁，2023年，2月20日，星期六上式表示dij(2)在dij(1)以及從頂點vi經(jīng)過頂點v2到vj的權(quán)之和di2(1)+d2j(1)兩者之中選擇最短長度。依此類推，迭代公式為：上式表示dij(m)在dij(m-1)以及從頂點vi經(jīng)過頂點vm到vj的權(quán)之和dim(m-1)+dmj(m-1)兩者之中選擇最短長度。當(dāng)m=n時結(jié)束迭代。

第13頁，共161頁，2023年，2月20日，星期六2．程序設(shè)計

先編寫Flody算法的子程序（函數(shù)）如下：Function[D,R]=floyd(a)n=size(a,1);D=a;%D是初始矩陣fori=1:n

forj=1:nR(i,j)=j;endend第14頁，共161頁，2023年，2月20日，星期六fork=1:nfori=1:nforj=1:nifD(i,k)+D(k,j)<D(i,j)

D(i,j)=D(i,k)+D(k,j);%在循環(huán)中進(jìn)行矩陣迭代

R(i,j)=R(i,k);%R是路徑矩陣endendendendD,R%輸出最短路矩陣和最短路的路徑矩陣。第15頁，共161頁，2023年，2月20日，星期六以上程序是通用程序，只需輸入初始距離矩陣，就能輸出最短路矩陣以及最短路的路徑矩陣，將程序以文件名floyd.m存盤。例1以2007年研究生數(shù)學(xué)建模競賽C題為例，已知16個郵政支局的初始距離矩陣，求任意兩個節(jié)點之間的最短路。解：編寫主程序如下：a=[0,27,44,17,11,27,42,inf,inf,inf,20,25,21,21,18,27,inf;…………inf,inf,inf,inf,30,inf,inf,inf,21,13,20,inf,inf,inf,inf,9,0];[D,R]=floyd(a);第16頁，共161頁，2023年，2月20日，星期六輸入數(shù)據(jù)中的inf表示無窮大（兩個頂點之間沒有邊直接相連）。運行以上程序，求得最短路矩陣D和最短路的路徑矩陣。此處省略結(jié)果。

第17頁，共161頁，2023年，2月20日，星期六§3最小生成樹第18頁，共161頁，2023年，2月20日，星期六一、最小生成樹的概念樹是圖論中的一種簡單而重要的圖，連通并且無圈的無向圖稱為樹，常用T表示。樹有以下性質(zhì)：(1)樹中任意兩點之間有唯一路徑；(2)樹的邊數(shù)等于頂點數(shù)減1；(3)在樹中刪去任意一條邊就不連通；(4)在樹中任意兩個不相鄰的頂點間添加一條邊，則恰好產(chǎn)生一個圈。第19頁，共161頁，2023年，2月20日，星期六具有n個頂點的無向連通圖是樹的充分必要條件是它有n-1條邊．連通圖G的子圖T，如果它的頂點集與G的頂點集相同，且T為樹，則稱T是圖G的生成樹，又稱支撐樹。如果圖的邊有權(quán)（對應(yīng)于邊的實數(shù)），則生成樹上各邊權(quán)的總和稱為生成樹的權(quán)，生成樹并不唯一，權(quán)達(dá)到最小的生成樹稱為最小生成樹(MinimalSpanningTree，簡稱MST)，最小生成樹不一定唯一．第20頁，共161頁，2023年，2月20日，星期六最小生成樹是網(wǎng)絡(luò)優(yōu)化中的一個重要問題，在網(wǎng)絡(luò)設(shè)計中有廣泛的應(yīng)用，例如如何修筑一些公路把若干個城鎮(zhèn)連接起來且總里程最短；如何架設(shè)通訊網(wǎng)絡(luò)將若干個地區(qū)連接起來且總費用最省；如何修筑水渠將水源和若干塊待灌溉的土地連接起來且總距離最短等等．這些應(yīng)用問題通稱為最優(yōu)連線問題，其實質(zhì)是尋找圖的最小生成樹．第21頁，共161頁，2023年，2月20日，星期六二、Prim（普里姆）算法求圖的最小生成樹最常用的算法有兩種：Prim（普里姆）算法和Kruskal（克羅斯克爾）算法，這兩種方法都由貪婪法的思想發(fā)展而來。貪婪法又稱貪心法，該法總是做出在當(dāng)前看來最好的選擇，也就是說該算法并不從整體最優(yōu)考慮，它所做出的選擇只是在某種意義上的局部最優(yōu)選擇。雖然貪婪算法不能對所有問題都得到整體最優(yōu)解，但是它對某些問題能夠得到整體最優(yōu)解，例如圖的固定起點的最短路問題，最小生成樹問題。有時候，即使貪婪算法不能得到整體最優(yōu)解，但其結(jié)果卻是整體最優(yōu)解的很好近似。第22頁，共161頁，2023年，2月20日，星期六Prim算法的思路是：把所有頂點分成部分（兩個集合），一個用S表示（該集合中的頂點都涂成紅色），另一個用V-S表示（該集合中的頂點都涂成白色），開始時S中只有一個頂點v1，其余頂點都是白色，在一個端點為紅色，另一個端點為白色的邊中選取權(quán)最小的邊，將該邊涂紅（表示入選最小生成樹）并且把該邊的白色端點也涂紅（表示移入S中）這個過程一直進(jìn)行下去，S中的端點越來越多，直到所有頂點都涂成紅色為止，或者說紅色邊達(dá)到n-1條為止。第23頁，共161頁，2023年，2月20日，星期六從Prim算法的思路中可以看出，該算法的關(guān)鍵是如何找出連接紅點和白點的所有邊中找出權(quán)最小的邊。若G為完全圖，當(dāng)前有k個紅點，則有n-k個白點，有k(n-k)條連接紅、白點的邊，為了在如此眾多的邊中找到權(quán)最小的邊，可以分兩步走，對每一個白點，先從連接該點至k個紅點的k條中找出權(quán)最小的邊作為候選邊，然后對n-k個白點，從n-k條候選邊中找出權(quán)最小的邊。第24頁，共161頁，2023年，2月20日，星期六實現(xiàn)Prim算法的Matlab編程思路如下：(1)設(shè)第一個紅點是節(jié)點v1。構(gòu)建初始候選邊的權(quán)矩陣B。該矩陣有3行，第一行表示當(dāng)前紅點，開始時第一個紅點是v1，故第一行都是1，第二行表示白點，開始時白點的序號是2,3,…,n，第三行表示連接紅點和白點的邊的權(quán)值。當(dāng)前入選最小生成樹的最短邊將從該矩陣中產(chǎn)生。初始最小生成樹T是空集。(2)對B矩陣的第3行排序，即對候選邊的權(quán)值進(jìn)行排序，選取最短邊（權(quán)值最小的邊），把該邊涂紅（選入最小生成樹的邊集T），該邊的白色端點也涂成紅色。第25頁，共161頁，2023年，2月20日，星期六(3)將(2)選出的邊移出B（不參與下一輪競選），即將它從B矩陣中刪除。當(dāng)前有n-2個白點（兩個紅點），對每個白點都有到兩個紅點的兩條邊，通過比較這兩者的大小，選出權(quán)值小的邊，放入B矩陣的相應(yīng)位置上，由此構(gòu)建新的候選邊矩陣B，此時B矩陣的有n-2列。(4)對新的B矩陣重復(fù)(2)和(3)，T中的邊將越來越多，B矩陣的列數(shù)越來越少，當(dāng)選入T中的紅色邊達(dá)到n-1條時結(jié)束運算，輸出T。第26頁，共161頁，2023年，2月20日，星期六按照以上思路編寫Matlab程序如下：function[T,e]=prim(a)T=[];%T為最小生成樹的邊集，開始為空集。e=0;%e是最小生成樹的長度，開始為0。v=1;%v表示第一個紅點是1號頂點。n=size(a,1);%n是總頂點數(shù)，它等于初始距離矩陣a的列數(shù)。c=2:n;%c代表所有白點，開始是2,3,…,n。第27頁，共161頁，2023年，2月20日，星期六forj=2:nb(1,j-1)=1;b(2,j-1)=j;

b(3,j-1)=a(1,j);end%以上一段程序生成3行n-1列的矩陣，存儲初始候選邊及其權(quán)值信息，該矩陣的第一行都是1，表示第一個紅色點是1號頂點，第二行表示白色點依次為2,3,…,n，第三行表示所有連接紅點和白點的邊的權(quán)值第28頁，共161頁，2023年，2月20日，星期六whilesize(T,2)<n-1%只要最小生成樹的邊數(shù)小于n-1就循環(huán)[m,i]=min(b(3,:));%從候選邊中找出權(quán)值最小的邊（其值存入變量m，序號為i）T(:,size(T,2)+1)=b(:,i);%當(dāng)前最短邊（含起點、終點和權(quán)值3個樹中）存入T中當(dāng)前列，表示入選最小生成樹

e=e+b(3,i);%累計最小生成樹的長度

v=b(2,i);%把新入選最小生成樹的邊的白色端點變成當(dāng)前紅點第29頁，共161頁，2023年，2月20日，星期六t=find(c==b(2,i));c(t)=[];%把該點從白點集合中移出去b(:,i)=[];%把該邊從候選邊中刪除

forj=1:length(c)d=a(v,b(2,j));ifd<b(3,j)b(1,j)=v;b(3,j)=d;endend第30頁，共161頁，2023年，2月20日，星期六%以上循環(huán)調(diào)整候選邊集合，入選該集合的邊數(shù)等于當(dāng)前白點數(shù)，對每一個白點入選一條邊，該邊通過比較連接該白點到紅點的邊的權(quán)值大小確定，小者入選。該循環(huán)是程序的關(guān)鍵和核心部分。endT,e以上程序以文件名prim.m存盤。第31頁，共161頁，2023年，2月20日，星期六例2以2007年研究生數(shù)學(xué)建模競賽C題為例，已知縣郵政局X1和16個郵政支局的初始距離矩陣，求該運輸圖的最小生成樹。解：在Matlab中輸入a=[0,27,44,17,11,27,42,inf,inf,inf,20,25,21,21,18,27,inf;……inf,inf,inf,inf,30,inf,inf,inf,21,13,20,inf,inf,inf,inf,9,0];[T,e]=prim(a);第32頁，共161頁，2023年，2月20日，星期六計算結(jié)果為：T=1567551116111016164111456784111617109151231314211139131415991011111419212121e=221T中每一列代表入選最小生成樹的一條邊，每一列有3個元素，前兩個代表頂點的編號，第3個是邊的權(quán)值。e是最小生成樹的總長。第33頁，共161頁，2023年，2月20日，星期六三、Kruskal（克羅斯克爾）算法Kruskal（克羅斯克爾）算法又稱“避圈法”，也是一種貪婪算法。給定加權(quán)連通圖G={V,E}，Kruskal算法的基本思路如下：(1)把所有邊按照權(quán)值的大小由小到大排序，將最小邊入選最小生成樹T。(2)從剩下的邊中選取權(quán)值最小的邊，并且該邊與T中已經(jīng)存在的邊不形成圈，將它也取進(jìn)T中（若某邊權(quán)值雖然小，但形成圈則舍去此邊，并且另選。重復(fù)步驟(2),直至入選T的邊達(dá)到n-1條為止。第34頁，共161頁，2023年，2月20日，星期六由以上思路可知，Kruskal算法的關(guān)鍵是如何判斷一條候選邊是否會與T中已有邊形成圈，下面介紹一種判斷方法。設(shè)所有頂點都是紅色，選入最小生成樹T的邊為紅色，沒有選入的邊為白色。則紅點和紅邊會形成一個或者一個以上的連通分支，它們都是G的子樹，當(dāng)一條待選邊的兩個端點屬于同一棵子樹時候就會形成圈，否則不構(gòu)成圈，且該邊入選后會使原來兩個不連通的紅色子樹合并成為一棵紅色連通子樹。因此判斷一條邊是否會與現(xiàn)有紅邊形成圈，只需要判斷該邊的兩個端點是否屬于同一棵子樹。第35頁，共161頁，2023年，2月20日，星期六可以用下面的方法來實現(xiàn)以上判斷：給每棵子樹一個不同的編號，對每一個頂點引入一個標(biāo)記t，表示該頂點所在子樹的編號。當(dāng)加入一條紅色邊時，就該邊兩個端點所在的子樹連接起來成為一棵子樹，從而兩棵子樹中的頂點標(biāo)記要改成一樣。第36頁，共161頁，2023年，2月20日，星期六按照以上思路編寫Matlab程序如下：function[T,c]=kruskal(a)n=size(a,1);%n是總頂點數(shù)m=0;fori=1:n-1forj=i+1:nifa(i,j)>0&a(i,j)<infm=m+1;b(1,k)=i;b(2,k)=j;b(3,k)=a(i,j);endendend第37頁，共161頁，2023年，2月20日，星期六%以上循環(huán)生成圖的邊權(quán)矩陣，該矩陣有3行，第1行和第2行是頂點的編號，第3行是邊的權(quán)值，矩陣的列數(shù)對于圖的邊數(shù)，每一列代表一條邊。程序運行以后，該矩陣的列數(shù)（即圖的總邊數(shù)記錄在變量m中）。[B,i]=sortrows(b',3);B=B';%實現(xiàn)對邊權(quán)矩陣按照權(quán)值大小由小到大排序，B是排序以后的邊權(quán)矩陣。k=0;%k表示已經(jīng)被選入最小生成樹的邊數(shù)t=1:n;%開始每個頂點各自為一棵獨立的子樹，子樹的編號分別1,2,…,n。T=[];c=0;%開始時最小生成樹為空集，權(quán)值之和為0第38頁，共161頁，2023年，2月20日，星期六fori=1:m%對排序以后的邊權(quán)矩陣，按順序考察每一條邊ift(B(1,i))~=t(B(2,i))%當(dāng)?shù)趇條邊的兩個端點所在子樹的編號不相等時，該邊與已經(jīng)選入最小生成樹的邊不形成圈，于是運行以下語句

k=k+1;%入選最小生成樹的邊數(shù)k增加1T(:,k)=B(:,i);%把該邊選入最小生成樹的集合Tc=c+B(3,i);%把該邊的權(quán)值加到最小生成樹的總權(quán)值之中

tmin=min(t(B(1,i)),t(B(2,i)));tmax=max(t(B(1,i)),t(B(2,i)));第39頁，共161頁，2023年，2月20日，星期六%入選邊的兩個端點分別屬于不同的子樹，t標(biāo)號不同，對這兩個t標(biāo)號排序forj=1:n

ift(j)==tmaxt(j)=tmin;

endend%將入選邊所屬兩個t標(biāo)號合并成一個（大標(biāo)號改為小標(biāo)號）end第40頁，共161頁，2023年，2月20日，星期六

ifk==n-1%如果入選最小生成樹的邊數(shù)達(dá)到n-1，則結(jié)束計算

break;endendT,c以上程序以文件名kruskal.m存盤。第41頁，共161頁，2023年，2月20日，星期六仍然以例2的數(shù)據(jù)為例，先輸入數(shù)據(jù)矩陣a，然后運行[T,e]=kruskal(a)得到計算結(jié)果。T=6111610191557412531127161711510166851611413141499910111111131314141519212121e=221該結(jié)果與Prim算法求出的結(jié)果相同。雖然Prim和kruskal兩種算法的思路都由貪婪法發(fā)展而來，但它們用來求最小生成樹時，最終輸出結(jié)果必定是最優(yōu)解。第42頁，共161頁，2023年，2月20日，星期六最小生成樹

的圖形第43頁，共161頁，2023年，2月20日，星期六四、用LINGO求最小生成樹1.把最小生成樹問題轉(zhuǎn)化為整數(shù)規(guī)劃采用一定的方法可以把最小生成樹問題轉(zhuǎn)化為整數(shù)規(guī)劃，然后用LINGO求解。節(jié)點1表示樹根，點i到點j的距離用Cij表示，當(dāng)兩個節(jié)點之間沒有線路相通時，兩點之間距離用M(很大的實數(shù))表示。引入0-1整數(shù)變量xij：若xij=1(且i≠j)表示從i到j(luò)的邊在樹中，xij＝0則表示該邊不在樹中。第44頁，共161頁，2023年，2月20日，星期六目標(biāo)函數(shù)約束條件：(1)除樹根外每個點都有線路通到(且只需要一次)表示為(2)至少有一條線路從1出來第45頁，共161頁，2023年，2月20日，星期六以上約束條件是必要條件，但不充分，類似于TSP問題，增加一個變量u，再附加約束條件：(1)限制uj的取值范圍為：u1=0，1≤uj≤n-1，j=2,3,...,n；用以下不等式可以達(dá)到目的：uj≥1且uj≤

n-1-(n-2)x1j，j>1，(2)如果線路從j到k，則uk=uj+1，且避免來回重復(fù)和圈，約束條件為:uj≥uk+xkj-(n-2)(1-xkj)+(n-3)xjk，1≤k≤n，2≤j≤nj≠k；第46頁，共161頁，2023年，2月20日，星期六最優(yōu)連線(最小生成樹)轉(zhuǎn)化為整數(shù)規(guī)劃：第47頁，共161頁，2023年，2月20日，星期六例3假設(shè)某電力公司計劃在七個村莊之間架設(shè)電線，各村莊之間的距離如圖所示．試求出使電線總長度最小的架線方案．第48頁，共161頁，2023年，2月20日，星期六2.LINGO程序編寫LINGO程序如下：MODEL:sets:city/1..7/:u;!定義7個城市;link(city,city):dist,x;!距離矩陣和決策變量;endsetsn=@size(city);data:!dist是距離矩陣;第49頁，共161頁，2023年，2月20日，星期六dist=034710010010030324100100430100571007210002100610045201410010071001021001001006420;!這里可改為你要解決的問題的數(shù)據(jù);enddata第50頁，共161頁，2023年，2月20日，星期六

min=@sum(link:dist*x);!目標(biāo)函數(shù);U(1)=0;@for(link:@bin(x));!定義X為0\1變量;@FOR(city(K)|K#GT#1:@sum(city(I)|I#ne#K:x(I,K))=1;@for(city(J)|J#gt#1#and#J#ne#K:

u(J)>=u(K)+X(K,J)-(N-2)*(1-X(K,J))+(N-3)*X(J,K);););@sum(city(J)|J#GT#1:x(1,J))>=1;

@for(city(K)|K#gt#1:U(K)>=1;U(K)<=N-1-(N-2)*X(1,K););end第51頁，共161頁，2023年，2月20日，星期六計算結(jié)果：目標(biāo)函數(shù)值(最優(yōu)連線的長度)為13，最優(yōu)連線的構(gòu)成如圖所示4123567第52頁，共161頁，2023年，2月20日，星期六§4旅行商問題第53頁，共161頁，2023年，2月20日，星期六一、旅行商問題的基本概念旅行商問題（又稱貨郎擔(dān)問題，travelingsalesmanproblem，簡稱TSP問題）是典型的組合優(yōu)化問題，并且是一個NP完全難題，其提法為：有n個城市，相互之間的旅行費用（或距離）為已知，有一個旅行推銷商，從某個基點城市出發(fā)，要遍訪其余n-1個城市至少一次，最后回到出發(fā)點，試找出總費用最?。ɑ蚩偮烦套疃蹋┑穆眯新肪€。稱能夠到每個城市至少一次的回路為旅行商回路，其中費用最少者為最優(yōu)旅行商回路.

第54頁，共161頁，2023年，2月20日，星期六在圖論中，經(jīng)過所有頂點恰好一次的圈（路）稱為哈密頓圈（路），簡稱H圈（H路），存在H圈的圖稱為哈密頓圖，簡稱H圖。旅行商問題是指在賦權(quán)圖上經(jīng)過每個頂點至少一次，且總長度（路徑上權(quán)的總和）達(dá)到最小的閉通路。在加權(quán)的連通無向圖中，權(quán)最小的H圈簡稱最優(yōu)H圈；經(jīng)過每個頂點至少一次且權(quán)最小的閉通路稱為最優(yōu)旅行商回路。注意：最優(yōu)H圈與最優(yōu)旅行商回路兩者是有區(qū)別的，最優(yōu)H圈只允許經(jīng)過每個頂點恰好一次，而最優(yōu)旅行商回路允許經(jīng)過某些頂點一次以上。第55頁，共161頁，2023年，2月20日，星期六定理1在加權(quán)圖G=（V，E）中，若對任意頂點x,y,z（z≠x,z≠y），都滿足w(x,y)≤w(x,z)+w(y,z)（三角形的兩邊之和大于等于第三邊，稱為三角不等式），則該圖的最優(yōu)哈密頓圈也是最優(yōu)旅行商回路。對于連通的非完全賦權(quán)圖G，先求出任意兩點之間的最短路，然后用最短路作為每一條邊的權(quán)，構(gòu)造一個以V為頂點集的完全圖G’=（V，E’），容易證明，在如此構(gòu)造出來的圖G’中，各邊的權(quán)自然滿足三角不等式，故在加權(quán)圖G中尋求最優(yōu)旅行商回路的問題就可以轉(zhuǎn)化為在圖G’中尋求最優(yōu)哈密頓圈的問題。第56頁，共161頁，2023年，2月20日，星期六尋找最優(yōu)哈密頓圈和最優(yōu)旅行商回路是圖論中的典型問題，而且是一個NP完全難題。問題的求解沒有多項式時間算法，除了窮舉法，目前還沒有尋找最優(yōu)解的算法，隨著頂點數(shù)的增加，運算所需時間呈指數(shù)級增長，當(dāng)頂點數(shù)較大時，求出最優(yōu)解所需時間可能是難以忍受的?？尚械姆椒ㄊ怯媒扑惴?，力爭在較短時間尋找接近最優(yōu)解的近似最優(yōu)解。旅行商問題得到了許多學(xué)者的關(guān)注和長期研究，提出了多種近似算法，例如分支定界法、遺傳算法、模擬退火法、蟻群算法、神經(jīng)網(wǎng)絡(luò)方法、粒子群優(yōu)化算法、重繞最小生成樹法、二次逐邊修正法等。第57頁，共161頁，2023年，2月20日，星期六二、用LINGO求解TSP問題的方法一1.把最優(yōu)哈密頓圈問題轉(zhuǎn)化為0-1線性規(guī)劃

將任意兩點之間的最短路作為兩點之間邊的權(quán)構(gòu)造完全圖G’。引入0-1整數(shù)變量xij(且i≠j)：若xij=1則邊i-j在回路中，而xij＝0則表示否。目標(biāo)函數(shù)首先必須滿足約束條件：對每個城市訪問一次且僅一次。從城市i出發(fā)一次(到其它城市去),表示為第58頁，共161頁，2023年，2月20日，星期六從某個城市到達(dá)j一次且僅一次，表示為：以上建立的模型類似于指派問題的模型，對TSP問題只是必要條件，并不充分。第59頁，共161頁，2023年，2月20日，星期六例如，用圖示路線連接六個城市，滿足以上兩個約束條件，但這樣的路線出現(xiàn)了兩個子回路，兩者之間不通，不構(gòu)成整體巡回路線。為此需要考慮增加充分的約束條件以避免產(chǎn)生子巡回。下面介紹一種方法：增加變量ui,i=2,3,…,n，（它的大小可以取正整數(shù)：例如從起點出發(fā)所達(dá)到的城市u=2,依此類推）。312456第60頁，共161頁，2023年，2月20日，星期六附加約束條件：ui-uj+nxij≤n-1,i=1,…,n，j=2,…,n，且i≠j

。下面證明：(1)任何含子巡回的路線都必然不滿足該約束條件（不管ui如何取值）；(2)全部不含子巡回的整體巡回路線都可以滿足該約束條件（只要ui取適當(dāng)值）。用反證法證明(1),假設(shè)存在子巡回，則至少有兩個子巡回。那么（必然）至少有一個子巡回中不含起點城市1，如上圖中的4－5－6－4，則必有

u4-u5+n≤n-1，u5-u6+n≤n-1，u6-u4+n≤n-1，把這三個不等式加起來得到n≤n-1，不可能，故假設(shè)不能成立。而對整體巡回，因為附加約束中j≥2,不包含起點城市1，故不會發(fā)生矛盾。第61頁，共161頁，2023年，2月20日，星期六對于整體巡回路線，只要ui取適當(dāng)值，都可以滿足該約束條件：(ⅰ)對于總巡回上的邊，xij=1,ui可取訪問城市i的順序數(shù)，則必有ui-uj＝-1，約束條件ui-uj+nxij≤n-1變成：-1+n≤n-1，必然成立。(ⅱ)對于非總巡回上的邊，因為xij=0，約束條件ui-uj+nxij≤n-1變成-1≤n-1，肯定成立。綜上所述，該約束條件只限止子巡回，不影響其它，于是TSP問題轉(zhuǎn)化成了一個整數(shù)線性規(guī)劃問題。第62頁，共161頁，2023年，2月20日，星期六求最優(yōu)哈密頓圈可以表示為規(guī)劃：第63頁，共161頁，2023年，2月20日，星期六2.LINGO程序!旅行售貨員問題;model:sets:city/1..17/:u;!定義17個城市;link(city,city):dist,!距離矩陣;x;!決策變量;endsetsn=@size(city);data:!距離矩陣;第64頁，共161頁，2023年，2月20日，星期六C=016.311.910.12812.9620.628.422.220.835.722.130.223.727.83616.3012.226.423.98.810.336.940.132.216.731.614.722.87.411.519.711.912.202236.1215.932.540.334.128.943.826.93519.617.625.810.126.422020.42316.110.518.312.115.228.132.238.433.837.946.12823.936.120.4015.1342416.28.37.27.724.31831.335.432.912.98.8212315.1018.933.531.323.47.922.89.217.316.220.328.5610.35.916.13418.9026.634.428.226.841.72533.117.721.83020.636.932.510.52433.526.607.815.725.731.742.74244.348.456.628.440.140.318.316.231.334.47.807.923.423.940.534.247.551.649.122.232.234.112.18.323.428.215.77.9015.51632.626.339.643.741.220.816.728.915.27.27.926.825.723.415.5014.917.125.224.128.236.435.731.643.828.17.722.841.731.723.91614.9018.410.325.733.425.222.114.726.932.224.39.22542.740.532.617.118.408.17.326.22330.222.83538.41817.333.14234.226.325.210.38.1015.423.114.923.77.419.633.831.316.217.744.347.539.624.125.77.315.4018.920.327.811.517.637.935.420.321.848.451.643.728.233.426.223.118.908.23619.725.846.132.928.53056.649.141.236.425.22314.920.38.20;第65頁，共161頁，2023年，2月20日，星期六!這里可改為你要解決的問題的數(shù)據(jù);enddata!目標(biāo)函數(shù);min=@sum(link:dist*x);@FOR(city(K):

!進(jìn)入城市K;

@sum(city(I)|I#ne#K:x(I,K))=1;

!離開城市K;

@sum(city(J)|J#ne#K:x(K,J))=1;);

!保證不出現(xiàn)子圈;第66頁，共161頁，2023年，2月20日，星期六

@for(city(I)|I#gt#1:

@for(city(J)|J#gt#1#and#I#ne#J:u(I)-u(J)+n*x(I,J)<=n-1););

!限制u的范圍以加速模型的求解，保證所加限制并不排除掉TSP問題的最優(yōu)解;

@for(city(I):u(I)<=n-1);

@for(link:@bin(x));!定義X為0\1變量;end第67頁，共161頁，2023年，2月20日，星期六計算結(jié)果：目標(biāo)函數(shù)值：159.3路線：1→7→3→16→17→14→13→15→2→6→11→12→5→10→9→8→4→1因為以上規(guī)劃是線性規(guī)劃，所以求解不費時，當(dāng)頂點數(shù)為20－30個時，一般幾分鐘就可以得到最優(yōu)解。利用LINGO軟件的強大優(yōu)化能力，不必研究旅行商問題的算法，通過編寫不太復(fù)雜的LINGO程序，能夠較快地解決實際問題，達(dá)到事半功倍的效果。

第68頁，共161頁，2023年，2月20日，星期六三、用LINGO求解TSP問題的方法二1.對城市排序，找出最優(yōu)排序在現(xiàn)實中的城市交通圖中，有些城市之間有直接道路，有些則沒有，如果兩點之間沒有直接的通路，則兩點之間的距離取最短路（經(jīng)過其它點），即用任意兩點之間的最短路Cij作為圖的距離矩陣，構(gòu)成一個完全圖G'，其任意一對頂點都有一條邊相連。圖G的最優(yōu)旅行商回路等價于圖G'的最優(yōu)哈密頓圈，此時形式上的環(huán)形巡回路線實際上個別點有可能不止經(jīng)過一次。第69頁，共161頁，2023年，2月20日，星期六設(shè)某個城市為旅行的出發(fā)地和終點（相當(dāng)于總部所在地），旅行者從該城市出發(fā)到其它n個城市各一次且僅一次，最后回到出發(fā)地。我們把行進(jìn)路線分成n步，每一步到一個城市（第n+1步返回出發(fā)地），于是一條旅行路線就相當(dāng)于n個城市的一種排列，n個城市共有n!種排列方式。排序不同則總里程（或費用）可能不同，總里程（或總費用）最小的排序就是我們要尋找的最優(yōu)路線。第70頁，共161頁，2023年，2月20日，星期六引入0-1型決策變量Xkj，下標(biāo)k表示旅行的步數(shù)，下標(biāo)j表示到達(dá)哪一個城市，Xkj=1表示旅行者第k個目的地（到達(dá)點）是城市j，Xkj=0則表示否。用lj表示總部到各城市的距離，用Cij表示城市i與城市j之間的最短路。從出發(fā)地到第1個點的路程為從最后一個點返回出發(fā)地的里程為

第71頁，共161頁，2023年，2月20日，星期六假設(shè)在第k步到達(dá)城市i，在第k+1步達(dá)到城市j，即Xki=Xk+1,j=1，則走過的里程為：

Cij·Xki·Xk+1,j從第1點到第n點走過的總里程為目標(biāo)函數(shù)為第72頁，共161頁，2023年，2月20日，星期六約束條件有以下2條：(1)每一步到達(dá)一個城市，即(2)每一個城市必須到一次且只需一次，即第73頁，共161頁，2023年，2月20日，星期六綜上所述，可以把最優(yōu)哈密頓圈問題轉(zhuǎn)化成如下非線性0-1

規(guī)劃第74頁，共161頁，2023年，2月20日，星期六以上規(guī)劃中允許包含其它約束條件。用LINGO可以求解該規(guī)劃，舉例如下。某縣郵局和10個鄉(xiāng)鎮(zhèn)支局組成該縣的郵政運輸網(wǎng)絡(luò)，已知縣局到各支局的距離和支局之間的距離矩陣（數(shù)據(jù)在程序中）。用一輛郵車完成郵件運輸任務(wù)，郵車從縣局出發(fā)到各支局去一次且只需一次，最后回到縣局，求總路程最短的行駛路線。解：本題是“旅行商”問題?？梢杂蒙厦娼榻B的方法求解。第75頁，共161頁，2023年，2月20日，星期六編寫LINGO程序如下：MODEL:SETS:CITY/1..10/:JL;STEP/1..10/;LINE(STEP,CITY):X;LINKS(CITY,CITY):C;ENDSETS第76頁，共161頁，2023年，2月20日，星期六DATA:JL=71,56,27,30,28,26,15,9,30,27;C=0,15,44,47,64,83,86,75,93,98 15,0,29,32,49,68,71,60,78,83 44,29,0,20,37,53,42,31,49,54 47,32,20,0,17,36,42,39,60,57 64,49,37,17,0,19,37,37,58,55 83,68,53,36,19,0,18,35,56,47 86,71,42,42,37,18,0,24,38,29 75,60,31,39,37,35,24,0,21,26 93,78,49,60,58,56,38,21,0,29 98,83,54,57,55,47,29,26,29,0;ENDDATA第77頁，共161頁，2023年，2月20日，星期六@FOR(LINE:@BIN(X));M1=@SIZE(STEP);@FOR(CITY(I):@SUM(STEP(N):X(N,I))=1);@FOR(STEP(N):@SUM(CITY(I):X(N,I))=1);L1=@SUM(CITY(I):(X(1,I)+X(M1,I))*JL(I));LX=@SUM(STEP(N)|N#LT#M1:@SUM(LINKS(I,J):C(I,J)*X(N,I)*X(N+1,J)));MIN=L1+LX;END第78頁，共161頁，2023年，2月20日，星期六在程序運行前需要對LINGO的參數(shù)作必要的設(shè)置。對于非線性規(guī)劃，LINGO提供兩種求解方法，一種是“GlobalSolver”（稱為全局優(yōu)化求解器），另一種是“MultistartSolver”（稱為多起點算法），全局優(yōu)化求解器優(yōu)點是確保找到全局最優(yōu)解，缺點是有時需要較長運行時間。多起點算法的優(yōu)點是節(jié)省運行時間，但不能保證找到的解就是全局最優(yōu)解，設(shè)置起點數(shù)多一些往往找到的解就是全局最優(yōu)解。點擊菜單“Options”，再打開全局優(yōu)化求解器“GlobalSolver”選項，可以選或不選“GlobalSolver”，當(dāng)選擇多起點算法“MultistartSolver”時，需要設(shè)置起點數(shù)，若選擇“SolverDecides”表示由LINGO決定。第79頁，共161頁，2023年，2月20日，星期六對以上程序，我們選擇“GlobalSolver”，點擊菜單“Options”，在全局優(yōu)化求解器“GlobalSolver”選項框內(nèi)打“√”，再點擊“確定”。運行以上程序，費時4分多鐘，得到最優(yōu)解：目標(biāo)函數(shù)值（總路程）260公里郵車的行駛路線為：縣局→8→9→10→7→6→5→4→1→2→3→縣局第80頁，共161頁，2023年，2月20日，星期六四、多旅行商（MTSP）問題1.

多旅行商問題的概念在現(xiàn)實中問題中，有時候不是由一人走遍所有點，而是由幾個人分工合作，每個人只到其中部分城市，每個點都有人來過一次且只需一次，事先不指定誰到哪些點，求出使總路程最小的旅行規(guī)劃（每個人的行走路線）。例如郵路規(guī)劃中，為了在允許的時間內(nèi)完成郵件運輸任務(wù)，縣局的郵車往往不止1輛，而是用若干輛郵車分工運輸，只要保證每個支局有郵車來過即可，為了節(jié)省行駛費用，需要規(guī)劃幾輛郵車的最佳路線。這就是多旅行商問題。第81頁，共161頁，2023年，2月20日，星期六多旅行商問題的提法如下：有n+1個城市，相互間的路程（或旅行費用）為已知，有k個旅行商都從總部所在城市出發(fā)，赴其它城市旅行推銷，分工遍歷其余n個城市，即每個城市各有任意一名旅行商來過一次且僅一次，最后都回到出發(fā)地，目標(biāo)是總路程最短或總費用最省。多旅行商問題在物流配送、郵路優(yōu)化等方面具有較高的實用價值，而在現(xiàn)實問題中，研究對象往往不是單純的旅行商問題，而要考慮各種約束條件，例如時間約束、載重量約束等等。研究這一類帶約束條件的多旅行商問題具有很強的現(xiàn)實意義。

第82頁，共161頁，2023年，2月20日，星期六在現(xiàn)實的多旅行商問題中，往往帶有約束條件，例如時間約束、載重量約束等等。帶約束條件的多旅行商問題具有廣泛現(xiàn)實意義，且是極具挑戰(zhàn)性的難題，我們?nèi)匀话阉D(zhuǎn)化為0-1非線性規(guī)劃并編成LINGO程序來求解。實例某縣郵政局管轄16個支局，已知縣局到各支局的距離以及16個支局之間的距離矩陣。寄達(dá)各支局和各支局收寄的郵件(袋)如下表所示：第83頁，共161頁，2023年，2月20日，星期六縣郵局和各支局分布圖第84頁，共161頁，2023年，2月20日，星期六每一輛郵車最多裝載65袋郵件，郵車的運行成本為3元/公里。試用最少郵車，并規(guī)劃郵車的行駛路線使總費用最省。分析：首先考慮最少郵車數(shù)量，由題目所給表中數(shù)據(jù)，寄達(dá)16個支局的郵件總數(shù)為176袋，從各支局收寄的郵件總數(shù)為170袋，每一輛郵車最多容納65袋郵件，至少需要176/65≈2.7輛郵車，由于郵車數(shù)量為整數(shù)，故最少需要3輛郵車。如果3輛郵車能夠完成郵件運輸任務(wù)，則3輛車就是郵車數(shù)量的最優(yōu)解。

第85頁，共161頁，2023年，2月20日，星期六運輸費用與行駛里程成正比，總里程最短對應(yīng)總費用最省。把16個支局放在一起作為一個整體考慮，找出3條郵路，每條郵路都從縣局出發(fā)，到若干支局進(jìn)行卸裝，最后回到縣局。各郵車路過的支局?jǐn)?shù)量未知，合理安排各郵車的行駛路線，由3輛郵車分別承包運輸，在滿足運載量約束前提下，把3條巡回路線的總里程最小作為優(yōu)化的目標(biāo)。該問題相當(dāng)于附帶約束條件的多旅行商模型。第86頁，共161頁，2023年，2月20日，星期六2.0-1規(guī)劃模型引入0-1型決策變量Xkj,Ykj,Zkj，分別表示3輛郵車第k步到達(dá)支局j，下標(biāo)k表示郵車行走的步數(shù)，下標(biāo)j表示到達(dá)哪一個支局，當(dāng)決策變量Xkj,Ykj,Zkj等于1時分別表示某郵車第k個裝卸點是支局j，等于0時表示否。設(shè)各郵車管轄的支局?jǐn)?shù)量分別為m1,m2,m3，則m1+m2+m3=16。約束條件有以下3條：(1)任何一輛車在任何一步到達(dá)一個支局

，即第87頁，共161頁，2023年，2月20日，星期六(2)任何一個支局必須有一輛郵車到達(dá)一次且只需要一次，即

(3)在郵車行進(jìn)的任何路段上，裝載的郵件不超過65袋。

設(shè)寄達(dá)各支局的郵件量為Pj，各支局收寄的郵件量為Qj。

裝載量是動態(tài)變化的，以第1輛郵車為例，出發(fā)時的裝載量為第88頁，共161頁，2023年，2月20日，星期六到第1個支局卸裝以后，裝載量變?yōu)樵谛旭傔^程中，裝載量的遞推公式為約束條件為第89頁，共161頁，2023年，2月20日，星期六綜上所述，建立多旅行商問題的0-1規(guī)劃模型如下：第90頁，共161頁，2023年，2月20日，星期六裝載量的計算公式為：第91頁，共161頁，2023年，2月20日，星期六3.LINGO程序編寫LINGO程序如下：MODEL:SETS:STATION/1..16/:JL,P,Q;STEPX/1..6/:WX;STEPY/1..5/:WY;STEPZ/1..5/:WZ;LINEX(STEPX,STATION):X;LINEY(STEPY,STATION):Y;LINEZ(STEPZ,STATION):Z;LINKS(STATION,STATION):C;ENDSETS第92頁，共161頁，2023年，2月20日，星期六DATA:JL=27361711243144403020252121182736;P=10,15,6,9,13,6,11,4,13,17,11,2,11,21,13,14;Q=9,14,5,10,9,10,13,9,15,9,6,7,13,15,10,16;C=031273851587167574752482141526131019332732456453476157524856632719014273447493929423838293844

3833140132033352515333232152430512727130921372626434545282938583234209013323235475252353342714547332113019303950656548444067644935373219011203154613425215753392526323011010204351241413474729152635392010018364114918

第93頁，共161頁，2023年，2月20日，星期六

526142334347503120180234625142348573832455265544336230272233422152383245526561514146270394857414829152835483424142522390112052563824293344251491433481109616344303842402113182342572090;ENDDATA第94頁，共161頁，2023年，2月20日，星期六@FOR(LINEX:@BIN(X));@FOR(LINEY:@BIN(Y));@FOR(LINEZ:@BIN(Z));M1=@SIZE(STEPX);M2=@SIZE(STEPY);M3=@SIZE(STEPZ);@FOR(STATION(I):@SUM(STEPX(N):X(N,I))+@SUM(STEPY(N):Y(N,I))+@SUM(STEPZ(N):Z(N,I))=1);@FOR(STEPX(N):@SUM(STATION(I):X(N,I))=1);@FOR(STEPY(N):@SUM(STATION(I):Y(N,I))=1);@FOR(STEPZ(N):@SUM(STATION(I):Z(N,I))=1);第95頁，共161頁，2023年，2月20日，星期六WX0=@SUM(STATION(I):P*@SUM(STEPX(N):X(N,I)));WY0=@SUM(STATION(I):P*@SUM(STEPY(N):Y(N,I)));WZ0=@SUM(STATION(I):P*@SUM(STEPZ(N):Z(N,I)));WX(1)=WX0-@SUM(STATION(J):(P(J)-Q(J))*X(1,J));WY(1)=WY0-@SUM(STATION(J):(P(J)-Q(J))*Y(1,J));WZ(1)=WZ0-@SUM(STATION(J):(P(J)-Q(J))*Z(1,J));@FOR(STEPX(N)|N#GE#2:WX(N)=WX(N-1)-@SUM(STATION(J):(P(J)-Q(J))*X(N,J)));@FOR(STEPY(N)|N#GE#2:WY(N)=WY(N-1)-@SUM(STATION(J):(P(J)-Q(J))*Y(N,J)));@FOR(STEPZ(N)|N#GE#2:WZ(N)=WZ(N-1)-@SUM(STATION(J):(P(J)-Q(J))*Z(N,J)));WX0<=65;WY0<=65;WZ0<=65;@FOR(STEPX(N):WX(N)<=65);@FOR(STEPY(N):WY(N)<=65);第96頁，共161頁，2023年，2月20日，星期六@FOR(STEPZ(N):WZ(N)<=65);L1=@SUM(STATION(I):(X(1,I)+X(M1,I))*JL(I));L2=@SUM(STATION(I):(Y(1,I)+Y(M2,I))*JL(I));L3=@SUM(STATION(I):(Z(1,I)+Z(M3,I))*JL(I));LX=@SUM(STEPX(N)|N#LT#M1:@SUM(LINKS(I,J):C(I,J)*X(N,I)*X(N+1,J)));LY=@SUM(STEPY(N)|N#LT#M2:@SUM(LINKS(I,J):C(I,J)*Y(N,I)*Y(N+1,J)));LZ=@SUM(STEPZ(N)|N#LT#M3:@SUM(LINKS(I,J):C(I,J)*Z(N,I)*Z(N+1,J)));MIN=L1+L2+L3+LX+LY+LZ;END第97頁，共161頁，2023年，2月20日，星期六三輛郵車各自負(fù)責(zé)的支局?jǐn)?shù)量有若干種分配方法，例如有6,5,5、6,6,4、7,5,4等不同分組法。經(jīng)過試驗，以6,5,5方案最優(yōu)。目標(biāo)函數(shù)值（3條郵路的總里程）為343km。第一條郵路：縣局→10→9→8→7→5→6→縣局，總里程121km，沿途各段郵件的裝載量為64,56,58,63,65,61,65袋。注意：如果支局5和6的先后次序倒過來，即走7→6→5→縣局，則里程為106km，減少15km，但是在支局6卸裝以后，郵件達(dá)69袋，超過了裝載量約束，看來先到支局5，后到支局6是因為避免超載的原因，被迫繞路，整體上仍然保持最優(yōu)。第98頁，共161頁，2023年，2月20日，星期六第二條郵路：縣局→14→15→16→11→12→縣局，總里程105km，沿途各段郵件的裝載量為61,55,52,54,49,54袋。第三條郵路：縣局→13→1→2→3→4→縣局，總里程117km，沿途各段郵件的裝載量為51,53,52,51,50,51袋。第99頁，共161頁，2023年，2月20日，星期六三條郵路的圖形如圖所示

第100頁，共161頁，2023年，2月20日，星期六§5中國郵遞員問題第101頁，共161頁，2023年，2月20日，星期六一、歐拉（Euler）圖

定義：設(shè)圖G={V,E}是連通無向圖，則經(jīng)過G的每邊正好一次的道路稱為歐拉道路（歐拉跡）；經(jīng)過G的每邊至少一次的閉通路稱為巡回；經(jīng)過G的每邊正好一次的巡回稱為歐拉巡回；存在歐拉巡回的圖稱為歐拉圖；定理：一個非空連通圖是歐拉圖的充分必要條件是它沒有奇點。推論：連通圖G能夠一筆畫出（存在歐拉跡）的充要條件是所有頂點是偶點或者僅有兩個頂點是奇點。第102頁，共161頁，2023年，2月20日，星期六二、中國郵遞員問題

1.概念郵遞員從郵局出發(fā)，經(jīng)過他所投遞范圍內(nèi)的每一條街道至少一次，然后返回郵局，如何安排投遞路線使總路程最短，這個問題由中國學(xué)者管梅谷于1962年首先提出并給出了一種解法，被國際上稱為中國郵遞員問題。用圖來描述投遞區(qū)域，用邊表示街道，用點表示路口和郵局，則投遞區(qū)構(gòu)成一個非負(fù)的賦權(quán)連通圖。中國郵遞員問題就是在一個非負(fù)的賦權(quán)連通圖中尋找一條總權(quán)最小的巡回，這種巡回稱為最優(yōu)巡回。

第103頁，共161頁，2023年，2月20日，星期六2．歐拉圖中的最優(yōu)巡回若圖G是歐拉圖，則G的任何一個歐拉巡回都是最優(yōu)巡回，因為歐拉巡回是一條通過G的每一條邊恰好一次的巡回。此時可用Fleury算法來確定一個歐拉巡回。定義：設(shè)G是連通圖，邊，若從G中刪除邊e后，圖不連通，則稱邊e為圖G的割邊。定理：e是G的割邊的充要條件是e不含在G的圈中。第104頁，共161頁，2023年，2月20日，星期六Fleury算法的基本思想：從任一點出發(fā)，每當(dāng)訪問一條邊時，先進(jìn)行檢查，如果可供訪問的邊不止一條，則應(yīng)選不是未訪問邊集構(gòu)成的子圖的割邊作為訪問邊直到?jīng)]有邊可供選擇為止。Fleury算法的步驟：(1)任意選取一個頂點v0，令W0=v0（作為起點）；(2)假設(shè)道路Wi=v0e1v1e2…eivi已經(jīng)選定，則按以下方法從E\{e1,e2,…,ei}中選取一條邊ei+1：①ei+1和vi相關(guān)聯(lián)；②除非沒有別的邊可選擇，否則ei+1不是Gi=G\{e1,e2,…,ei}的割邊。③當(dāng)?shù)冖诓讲荒苓M(jìn)行時就停止。

第105頁，共161頁，2023年，2月20日，星期六3．非歐拉圖中的最優(yōu)巡回如果G不是歐拉圖（圖中有奇點），則G的任何一個巡回經(jīng)過某些（與奇點相關(guān)聯(lián)的）邊必定多于一次。解決這一類問題的一般方法是，引入重復(fù)邊，使原圖成為歐拉圖，并且添加的重復(fù)邊的權(quán)的總和為最小。情形1G只有兩個奇點u和v，求最優(yōu)巡回的算法如下：(1)用Dijkstra算法或Floyd算法求出奇點u和v之間的最短路徑P。(2)令G*=G∪P，則G*為歐拉圖。(3)用Fleury算法來確定一個G*的歐拉巡回，這就是G的最優(yōu)巡回。第106頁，共161頁，2023年，2月20日，星期六情形2

G有2n個奇點（n>1），可以用Edmonds算法解決，其基本思路為：首先將奇點配對，使配對以后各對之間距離的總和（兩點之間的距離按照最短路計算）達(dá)到最?。ǚQ為最佳配對）,求最佳配對的方法可以用匈牙利法或0-1規(guī)劃法等方法（可以用Lingo實現(xiàn)）。然后把每一對點之間的最短路作為邊添加到原圖中,使之成為歐拉圖G*，找出G*的歐拉巡回就是原圖的最佳巡回。第107頁，共161頁，2023年，2月20日，星期六算法步驟如下：(1)用Floyd算法求出所有奇點之間的最短路徑和距離矩陣。(2)用匈牙利法或0-1規(guī)劃法求出所有奇點之間的最佳配對。(3)在原圖上添加最佳配對所包含的兩兩頂點之間的最短路得到歐拉圖G*。(4)用Fleury算法確定一個G*的歐拉巡回，這就是G的最優(yōu)巡回。

第108頁，共161頁，2023年，2月20日，星期六三、Fleury算法的Matlab程序

設(shè)圖是連通無向圖，如果所有頂點都是偶點，則該圖是歐拉圖，必然存在歐拉巡回，如果恰好有兩個奇次頂點，則稱該圖為半歐拉圖，必然存在起點在奇點（兩個奇點中的一個）且終點在另一個奇點的歐拉道路。這兩種情況下都可用fleury算法確定一條歐拉巡回或者歐拉道路。第109頁，共161頁，2023年，2月20日，星期六按照fleury算法的思路編寫Matlab程序。主要程序arEuler根據(jù)圖的邊集確定是否為歐拉圖、半歐拉圖或非歐拉圖，如果是歐拉圖則用fleury算法找到一條歐拉巡回路線（歐拉圖的歐拉巡回不止一條，輸出的是其中的一條），如果是半歐拉圖則返回一條歐拉道路，其起點在兩個奇點之一，終點是另一個奇點。第110頁，共161頁，2023年，2月20日，星期六function[eu,cEu]=arEuler(E)%輸入?yún)?shù)E是圖的邊集（m行2列矩陣，每一行的兩個數(shù)字代表一條邊的兩個頂點，共有m條邊），輸出參數(shù)eu有三種結(jié)果：若為歐拉圖則eu=1；半歐拉圖則eu=0.5；否則eu=0。輸出參數(shù)cEu是m行1列矩陣，表示歐拉巡回或歐拉道路中邊的序列。eu=0;%eu的初始值為0cEu=[];%cEu開始時為空集ncV=arComp(E);%調(diào)用函數(shù)arComp確定圖的分枝構(gòu)成，判斷是否連通

第111頁，共161頁，2023年，2月20日，星期六ifmax(ncV)>1,%表示有2個或以上互不連通的部分

return%不是連通圖就返回endn=max(max(E(:,1:2)));%n是圖的頂點總數(shù)m=size(E,1);%m是邊的總數(shù)第112頁，共161頁，2023年，2月20日，星期六fori=1:n

b(i)=0;forj=1:mifE(j,1)==i|E(j,2)==ib(i)=b(i)+1;endendend%b表示各頂點的度數(shù)第113頁，共161頁，2023年，2月20日，星期六rp=rem(b,2);%各頂點的度數(shù)除2取余數(shù)，偶點的余數(shù)為0，奇點的余數(shù)為1srp=sum(rp);%srp是rp的總和switchsrpcase0,%若余數(shù)的總和為0，則所有頂點為偶點，原圖是歐拉圖

eu=1;case2,%恰好有兩個奇點，原圖是半歐拉圖

eu=0.5;otherwise,%否則是非歐拉圖

return第114頁，共161頁，2023年，2月20日，星期六end%以下程序?qū)ふ乙粭l歐拉巡回或歐拉道路

ifsrp==0,%對于歐拉圖

v1=1;%把第一個頂點作為歐拉巡回的起點

else%對于半歐拉圖

v1=find(rp);%先找出奇點

v1=v1(1);%把第一個奇點作為歐拉道路的起點

end第115頁，共161頁，2023年，