計(jì)算機(jī)系統(tǒng)中圖與網(wǎng)路分析

圖與網(wǎng)路分析圖是最直觀模型1計(jì)算機(jī)系統(tǒng)中圖與網(wǎng)路分析第1頁(yè)BACD圖論GraphTheory哥尼斯堡七橋問(wèn)題(K?nigsbergBridgeProblem)LeonhardEuler(1707-1783)在1736年發(fā)表第一篇圖論方面論文，奠基了圖論中一些基本定理很多問(wèn)題都能夠用點(diǎn)和線來(lái)表示，普通點(diǎn)表示實(shí)體，線表示實(shí)體間關(guān)聯(lián)2計(jì)算機(jī)系統(tǒng)中圖與網(wǎng)路分析第2頁(yè)6.1圖與網(wǎng)路基本概念6.1.1圖與網(wǎng)路節(jié)點(diǎn)(Vertex)物理實(shí)體、事物、概念普通用vi

表示邊(Edge)節(jié)點(diǎn)間連線，表示相關(guān)系普通用eij

表示圖(Graph)節(jié)點(diǎn)和邊集合普通用G(V,E)表示點(diǎn)集V={v1,v2,…,vn}邊集E={eij}網(wǎng)路(Network)邊上含有表示連接強(qiáng)度權(quán)值，如wij又稱加權(quán)圖(Weightedgraph)3計(jì)算機(jī)系統(tǒng)中圖與網(wǎng)路分析第3頁(yè)6.1.2無(wú)向圖與有向圖邊都沒(méi)有方向圖稱為無(wú)向圖，如圖6.1在無(wú)向圖中eij=eji，或(vi,vj)=(vj,vi)當(dāng)邊都有方向時(shí)，稱為有向圖，用G(V,A)表示在有向圖中，有向邊又稱為弧，用aij表示，i,j次序是不能顛倒，圖中弧方向用箭頭標(biāo)識(shí)圖中現(xiàn)有邊又有弧，稱為混合圖4計(jì)算機(jī)系統(tǒng)中圖與網(wǎng)路分析第4頁(yè)

6.1.3端點(diǎn)，關(guān)聯(lián)邊，相鄰，次圖中能夠只有點(diǎn)，而沒(méi)有邊；而有邊必有點(diǎn)若節(jié)點(diǎn)vi,vj之間有一條邊eij，則稱vi,vj是eij端點(diǎn)(endvertex)，而eij是節(jié)點(diǎn)vi,vj關(guān)聯(lián)邊(incidentedge)同一條邊兩個(gè)端點(diǎn)稱為相鄰(adjacent)節(jié)點(diǎn)，含有共同端點(diǎn)邊稱為相鄰邊一條邊兩個(gè)端點(diǎn)相同，稱為自環(huán)(self-loop)；含有兩個(gè)共同端點(diǎn)兩條邊稱為平行邊(paralleledges)既沒(méi)有自環(huán)也沒(méi)有平行邊圖稱為簡(jiǎn)單圖(simplegraph)在無(wú)向圖中，與節(jié)點(diǎn)相關(guān)聯(lián)邊數(shù)目，稱為該節(jié)點(diǎn)“次”(degree)，記為d；次數(shù)為奇數(shù)點(diǎn)稱為奇點(diǎn)(odd),次數(shù)為偶數(shù)點(diǎn)稱為偶點(diǎn)(even)；圖中都是偶點(diǎn)圖稱為偶圖(evengraph)5計(jì)算機(jī)系統(tǒng)中圖與網(wǎng)路分析第5頁(yè)

6.1.3端點(diǎn)，關(guān)聯(lián)邊，相鄰，次有向圖中，由節(jié)點(diǎn)指向外弧數(shù)目稱為正次數(shù)，記為d+，指向該節(jié)點(diǎn)弧數(shù)目稱為負(fù)次數(shù)，記為d–次數(shù)為0點(diǎn)稱為孤立點(diǎn)(isolatedvertex)

，次數(shù)為1點(diǎn)稱為懸掛點(diǎn)(pendantvertex)定理1：圖中奇點(diǎn)個(gè)數(shù)總是偶數(shù)個(gè)

6.1.4鏈，圈，路徑，回路，歐拉回路相鄰節(jié)點(diǎn)序列

{v1

,v2

,…,vn

}組成一條鏈(link)，又稱為行走(walk)；首尾相連鏈稱為圈(loop)，或閉行走在無(wú)向圖中，節(jié)點(diǎn)不重復(fù)出現(xiàn)鏈稱為路徑(path)；在有向圖中，節(jié)點(diǎn)不重復(fù)出現(xiàn)且鏈中全部弧方向一致，則稱為有向路徑(directedpath)首尾相連路徑稱為回路(circuit)；6計(jì)算機(jī)系統(tǒng)中圖與網(wǎng)路分析第6頁(yè)6.1.4鏈，圈，路徑，回路，連通圖走過(guò)圖中全部邊且每條邊僅走一次閉行走稱為歐拉回路定理2：偶圖一定存在歐拉回路(一筆畫定理)

6.1.4連通圖，子圖，成份設(shè)有兩個(gè)圖G1(V1,E1),G2(V2,E2),若V2

V1,E2

E1，則G2是G1子圖無(wú)向圖中，若任意兩點(diǎn)間最少存在一條路徑，則稱為連通圖(connectedgraph)，不然為非連通圖(discon-nectedgraph)；非連通圖中每個(gè)連通子圖稱為成份(component)鏈，圈，路徑(簡(jiǎn)稱路)，回路都是原圖子圖平面圖(planargraph)，若在平面上能夠畫出該圖而沒(méi)有任何邊相交7計(jì)算機(jī)系統(tǒng)中圖與網(wǎng)路分析第7頁(yè)6.2樹(shù)圖與最小生成樹(shù)普通研究無(wú)向圖樹(shù)圖：倒置樹(shù)，根(root)在上，樹(shù)葉(leaf)在下多級(jí)輻射制電信網(wǎng)絡(luò)、管理指標(biāo)體系、家譜、分類學(xué)、組織結(jié)構(gòu)等都是經(jīng)典樹(shù)圖8計(jì)算機(jī)系統(tǒng)中圖與網(wǎng)路分析第8頁(yè)6.2.1樹(shù)定義及其性質(zhì)任兩點(diǎn)之間有且只有一條路徑圖稱為樹(shù)(tree)，記為T

樹(shù)性質(zhì)：最少邊連通子圖，樹(shù)中必不存在回路任何樹(shù)必存在次數(shù)為1點(diǎn)含有n個(gè)節(jié)點(diǎn)樹(shù)T邊恰好為n

1條，反之，任何有n個(gè)節(jié)點(diǎn)，n

1條邊連通圖必是一棵樹(shù)6.2.2圖生成樹(shù)樹(shù)T是連通圖G生成樹(shù)(spanningtree)，若T是G子圖且包含圖G全部節(jié)點(diǎn)；包含圖G中部分指定節(jié)點(diǎn)樹(shù)稱為steinertree每個(gè)節(jié)點(diǎn)有唯一標(biāo)號(hào)圖稱為標(biāo)識(shí)圖，標(biāo)識(shí)圖生成樹(shù)稱為標(biāo)識(shí)樹(shù)(labeledtree)Caylay定理：n(

2)個(gè)節(jié)點(diǎn)，有nn

2個(gè)不一樣標(biāo)識(shí)樹(shù)9計(jì)算機(jī)系統(tǒng)中圖與網(wǎng)路分析第9頁(yè)

6.2.2圖生成樹(shù)怎樣找到一棵生成樹(shù)深探法(depthfirstsearch)：任選一點(diǎn)標(biāo)識(shí)為0點(diǎn)開(kāi)始搜索，選一條未標(biāo)識(shí)邊走到下一點(diǎn)，該點(diǎn)標(biāo)識(shí)為1，將走過(guò)邊標(biāo)識(shí)；假設(shè)已標(biāo)識(shí)到i點(diǎn)，總是從最新標(biāo)識(shí)點(diǎn)向下搜索，若從i點(diǎn)無(wú)法向下標(biāo)識(shí)，即與i點(diǎn)相關(guān)聯(lián)邊都已標(biāo)識(shí)或相鄰節(jié)點(diǎn)都已標(biāo)識(shí)，則退回到

i

1點(diǎn)繼續(xù)搜索，直到全部點(diǎn)都被標(biāo)識(shí)廣探法(breadthfirstsearch)：是一個(gè)有層級(jí)結(jié)構(gòu)搜索，普通得到是樹(shù)形圖10計(jì)算機(jī)系統(tǒng)中圖與網(wǎng)路分析第10頁(yè)6.2.3最小生成樹(shù)有n個(gè)鄉(xiāng)村，各村間道路長(zhǎng)度是已知，怎樣敷設(shè)光纜線路使n個(gè)鄉(xiāng)村連通且總長(zhǎng)度最短顯然，這要求在已知邊長(zhǎng)度網(wǎng)路圖中找最小生成樹(shù)

最小生成樹(shù)算法：Kruskal

算法：將圖中全部邊按權(quán)值從小到大排列，依次選所剩最小邊加入邊集T，只要不和前面加入邊組成回路，直到T中有n

1條邊，則T是最小生成樹(shù)Kruskal

算法基于下述定理定理3指定圖中任一點(diǎn)vi，假如vj是距vi最近相鄰節(jié)點(diǎn)，則關(guān)聯(lián)邊eij必在某個(gè)最小生成樹(shù)中。推論將網(wǎng)路中節(jié)點(diǎn)劃分為兩個(gè)不相交集合V1和V2，V2=V

V1，則V1和V2間權(quán)值最小邊必定在某個(gè)最小生成樹(shù)中。11計(jì)算機(jī)系統(tǒng)中圖與網(wǎng)路分析第11頁(yè)6.2.3最小生成樹(shù)最小生成樹(shù)不一定唯一定理3推論是一個(gè)結(jié)構(gòu)性定理，它指示了找最小生成樹(shù)有效算法Prim

算法：不需要對(duì)邊權(quán)排序，即能夠直接在網(wǎng)路圖上操作，也能夠在邊權(quán)矩陣上操作，后者適累計(jì)算機(jī)運(yùn)算

邊權(quán)矩陣上Prim算法：1、依據(jù)網(wǎng)路寫出邊權(quán)矩陣，兩點(diǎn)間若沒(méi)有邊，則用表示；2、從v1開(kāi)始標(biāo)識(shí)，在第一行打，劃去第一列；3、從全部打行中找出還未劃掉最小元素，對(duì)該元素畫圈，劃掉該元素所在列，與該列數(shù)對(duì)應(yīng)行打；4、若全部列都劃掉，則已找到最小生成樹(shù)(全部畫圈元素所對(duì)應(yīng)邊)；不然，返回第3步。該算法中，打行對(duì)應(yīng)節(jié)點(diǎn)在V1中，未劃去列在V2中12計(jì)算機(jī)系統(tǒng)中圖與網(wǎng)路分析第12頁(yè)6.2.3最小生成樹(shù)Prim算法是多項(xiàng)式算法Prim算法能夠求最大生成樹(shù)網(wǎng)路邊權(quán)能夠有各種解釋，如效率次數(shù)受限最小生成樹(shù)—尚無(wú)有效算法最小Steiner樹(shù)—尚無(wú)有效算法

13計(jì)算機(jī)系統(tǒng)中圖與網(wǎng)路分析第13頁(yè)6.3

最短路問(wèn)題

6.3.1狄克斯特拉算法(Dijkstraalgorithm,1959)計(jì)算兩節(jié)點(diǎn)之間或一個(gè)節(jié)點(diǎn)到全部節(jié)點(diǎn)之間最短路令dij

表示vi到vj直接距離(兩點(diǎn)之間有邊)，若兩點(diǎn)之間沒(méi)有邊，則令dij

=，若兩點(diǎn)之間是有向邊，則dji

=；令dii

=0，s表示始點(diǎn)，t表示終點(diǎn)0、令始點(diǎn)Ts=0，并用框住，全部其它節(jié)點(diǎn)暫時(shí)標(biāo)識(shí)Tj=；1、從vs出發(fā)，對(duì)其相鄰節(jié)點(diǎn)vj1進(jìn)行暫時(shí)標(biāo)識(shí)，有Tj1=ds,j1；2、在全部暫時(shí)標(biāo)識(shí)中找出最小者，并用框住，設(shè)其為vr。若此時(shí)全部節(jié)點(diǎn)都永久標(biāo)識(shí)，算法結(jié)束；不然到下一步；3、從新永久標(biāo)識(shí)節(jié)點(diǎn)vr出發(fā)，對(duì)其相鄰暫時(shí)標(biāo)識(shí)節(jié)點(diǎn)進(jìn)行再標(biāo)識(shí)，設(shè)vj2為其相鄰節(jié)點(diǎn)，則Tj2=min{Tj2,Tr+dr,j2}，返回第2步。14計(jì)算機(jī)系統(tǒng)中圖與網(wǎng)路分析第14頁(yè)例1狄克斯特拉算法0

81510121511311315計(jì)算機(jī)系統(tǒng)中圖與網(wǎng)路分析第15頁(yè)

Dijkstra最短路算法特點(diǎn)和適應(yīng)范圍一個(gè)隱階段動(dòng)態(tài)規(guī)劃方法每次迭代只有一個(gè)節(jié)點(diǎn)取得永久標(biāo)識(shí)，若有兩個(gè)或兩個(gè)以上節(jié)點(diǎn)暫時(shí)標(biāo)識(shí)同時(shí)最小，可任選一個(gè)永久標(biāo)識(shí)；總是從一個(gè)新永久標(biāo)識(shí)開(kāi)始新一輪暫時(shí)標(biāo)識(shí)，是一個(gè)深探法被框住永久標(biāo)識(shí)Tj表示vs

到vj

最短路，所以要求dij0，第k次迭代得到永久標(biāo)識(shí)，其最短路中最多有k條邊，所以最多有n1

次迭代能夠應(yīng)用于簡(jiǎn)單有向圖和混合圖，在暫時(shí)標(biāo)識(shí)時(shí)，所謂相鄰必須是箭頭指向節(jié)點(diǎn)；若第n1

次迭代后仍有節(jié)點(diǎn)標(biāo)識(shí)為，則表明vs

到該節(jié)點(diǎn)無(wú)有向路徑假如只求vs到vt

最短路，則當(dāng)vt得到永久標(biāo)識(shí)算法就結(jié)束了；但算法復(fù)雜度是一樣應(yīng)用Dijkstra算法n1

次，能夠求全部點(diǎn)間最短路vs到全部點(diǎn)最短路也是一棵生成樹(shù)，但不是最小生成樹(shù)16計(jì)算機(jī)系統(tǒng)中圖與網(wǎng)路分析第16頁(yè)6.3.2Warshall-Floyd算法(1962)Warshall-Floyd算法能夠處理有負(fù)權(quán)值邊(弧)最短路問(wèn)題該算法是一個(gè)整體算法，一次求出全部點(diǎn)間最短路該算法不允許有負(fù)權(quán)值回路，但能夠發(fā)覺(jué)負(fù)權(quán)值回路該算法基于基本三角運(yùn)算定義對(duì)給定點(diǎn)間初始距離矩陣{dij}，令dii=，對(duì)全部i。對(duì)一個(gè)固定點(diǎn)j，運(yùn)算dik=min{dik,dij+djk},對(duì)全部i,k

j,稱為三角運(yùn)算。(注意，這里允許i=k)定理依次對(duì)j=1,2,…,n執(zhí)行三角運(yùn)算，則dik最終等于i

到k間最短路長(zhǎng)度。17計(jì)算機(jī)系統(tǒng)中圖與網(wǎng)路分析第17頁(yè)6.3.2Floyd-Warshall算法(1962)fori=1tondodii=;foralleij=0;forj=1tondofori=1tondoifi

jthenfork=1tondoifk

jthenbegin

dik=min{dik,dij+djk};

ifdik>dij+djktheneik=j

end;若網(wǎng)路中存在負(fù)回路，則計(jì)算中，一些dii會(huì)小于0，此時(shí)應(yīng)中止算法顯然，F(xiàn)loyd算法要進(jìn)行n(n-1)2次加法和比較怎樣回溯找出任兩點(diǎn)之間最短路？在Floyd算法中設(shè)一伴隨矩陣E={eik}，eik統(tǒng)計(jì)了i到

k最短路中最終一個(gè)中間節(jié)點(diǎn)18計(jì)算機(jī)系統(tǒng)中圖與網(wǎng)路分析第18頁(yè)小結(jié)最短路有廣泛應(yīng)用(6.3.4節(jié)市話局?jǐn)U容方案)最短路各種形式：無(wú)向圖，有向圖無(wú)循環(huán)圈，有向圖，混合圖，無(wú)負(fù)邊權(quán)，有負(fù)邊權(quán)，有負(fù)回路，k-最短路等當(dāng)存在負(fù)權(quán)值邊時(shí)，F(xiàn)loyd算法比Dijkstra算法效率高，且程序極簡(jiǎn)單。但Dijkstra算法靈活若圖是前向，則Dijkstra算法也能夠求兩點(diǎn)間最長(zhǎng)路普通情況下，兩點(diǎn)間最長(zhǎng)路是NP-complete，但最短路是P算法兩點(diǎn)間k-最短路：分為邊不相交和邊相交

求邊不相交k-最短路非常輕易：先求最短路，將該最短路中邊從網(wǎng)路刪去，再用Dijkstra算法可求次最短路，以這類推19計(jì)算機(jī)系統(tǒng)中圖與網(wǎng)路分析第19頁(yè)6.4網(wǎng)路最大流和最小截

6.4.1網(wǎng)路最大流概念網(wǎng)路流普通在有向圖上討論定義網(wǎng)路上支路容量為其最大經(jīng)過(guò)能力，記為cij，支路上實(shí)際流量記為fij圖中要求一個(gè)發(fā)點(diǎn)s，一個(gè)收點(diǎn)t節(jié)點(diǎn)沒(méi)有容量限制，流在節(jié)點(diǎn)不會(huì)存放容量限制條件：0

fij

cij平衡條件：滿足上述條件網(wǎng)路流稱為可行流，總存在最大可行流當(dāng)支路上fij=cij

，稱為飽和弧最大流問(wèn)題也是一個(gè)線性規(guī)劃問(wèn)題viA(vi)B(vi)20計(jì)算機(jī)系統(tǒng)中圖與網(wǎng)路分析第20頁(yè)6.4.2截集與截集容量定義：把網(wǎng)路分割為兩個(gè)成份弧最小集合，其中一個(gè)成份包含s點(diǎn)，另一個(gè)包含t點(diǎn)。普通包含s點(diǎn)成份中節(jié)點(diǎn)集適用V表示，包含t點(diǎn)成份中節(jié)點(diǎn)集適用V表示截集容量是指截集中正向弧容量之和

福特-富克森定理：網(wǎng)路最大流等于最小截集容量21計(jì)算機(jī)系統(tǒng)中圖與網(wǎng)路分析第21頁(yè)6.4.3確定網(wǎng)路最大流標(biāo)號(hào)法從任一個(gè)初始可行流出發(fā)，如0流基本算法：找一條從s到t點(diǎn)增廣鏈(augmentingpath)若在當(dāng)前可行流下找不到增廣鏈，則已得到最大流增廣鏈中與s到t方向一致弧稱為前向弧，反之后向弧

增廣過(guò)程：前向弧f

ij=fij+q,后向弧f

ij=fij

q

增廣后仍是可行流

22計(jì)算機(jī)系統(tǒng)中圖與網(wǎng)路分析第22頁(yè)最大流最小截標(biāo)號(hào)法步驟第一步：標(biāo)號(hào)過(guò)程，找一條增廣鏈1、給源點(diǎn)s標(biāo)號(hào)[s+,q(s)=]，表示從s點(diǎn)有沒(méi)有限流出潛力2、找出與已標(biāo)號(hào)節(jié)點(diǎn)i相鄰全部未標(biāo)號(hào)節(jié)點(diǎn)j，若(1)(i,j)是前向弧且飽和，則節(jié)點(diǎn)j

不標(biāo)號(hào)；(2)(i,j)是前向弧且未飽和，則節(jié)點(diǎn)j

標(biāo)號(hào)為[i+,q(j)]，表示從節(jié)點(diǎn)i正向流出，可增廣q(j)=min[q(i),cij

fij]；(3)(j,i)是后向弧，若fji=0，則節(jié)點(diǎn)j不標(biāo)號(hào)；(4)(j,i)是后向弧，若fji>0，則節(jié)點(diǎn)j標(biāo)號(hào)為[i

,q(j)]，表示從節(jié)點(diǎn)j

流向i，可增廣q(j)=min[q(i),fji]；3、重復(fù)步驟2，可能出現(xiàn)兩種情況：(1)節(jié)點(diǎn)t還未標(biāo)號(hào)，但無(wú)法繼續(xù)標(biāo)識(shí)，說(shuō)明網(wǎng)路中已不存在增廣鏈，當(dāng)前流v(f)就是最大流；全部獲標(biāo)號(hào)節(jié)點(diǎn)在V中，未獲標(biāo)號(hào)節(jié)點(diǎn)在V中，V與V間弧即為最小截集；算法結(jié)束(2)節(jié)點(diǎn)t取得標(biāo)號(hào)，找到一條增廣鏈，由節(jié)點(diǎn)t標(biāo)號(hào)回溯可找出該增廣鏈；到第二步23計(jì)算機(jī)系統(tǒng)中圖與網(wǎng)路分析第23頁(yè)最大流最小截標(biāo)號(hào)法步驟第二步：增廣過(guò)程1、對(duì)增廣鏈中前向弧，令f=f+q(t)，q(t)為節(jié)點(diǎn)t標(biāo)識(shí)值2、對(duì)增廣鏈中后向弧，令f=f

q(t)3、非增廣鏈上全部支路流量保持不變第三步：抹除圖上全部標(biāo)號(hào)，回到第一步以上算法是按廣探法描述，但在實(shí)際圖上作業(yè)時(shí)，按深探法進(jìn)行更加快捷一次只找一條增廣鏈，增廣一次換一張圖最終一次用廣探法，方便找出最小截集24計(jì)算機(jī)系統(tǒng)中圖與網(wǎng)路分析第24頁(yè)最大流最小截集標(biāo)號(hào)法舉例(s+,)(s+,6)(2

,6)(3+,1)(4+,1)(s+,)(s+,5)(2+,2)(5

,2)(4+,2)25計(jì)算機(jī)系統(tǒng)中圖與網(wǎng)路分析第25頁(yè)最大流最小截集標(biāo)號(hào)法舉例(s+,)(s+,3)(2

,3)最小截集26計(jì)算機(jī)系統(tǒng)中圖與網(wǎng)路分析第26頁(yè)最大流標(biāo)號(hào)法復(fù)雜度討論找一條增廣鏈計(jì)算量是輕易預(yù)計(jì)，不會(huì)超出O(n2)不過(guò)最多迭代多少次(即增廣次數(shù))就極難預(yù)計(jì)，在最壞情況下，與邊容量相關(guān)；如上圖：先增廣suvt,然后增廣svut，每次只能增廣1個(gè)單位，故要增廣4000次才能結(jié)束克服這種缺點(diǎn)經(jīng)驗(yàn)方法：盡可能先用段數(shù)少增廣鏈盡可能不重復(fù)前面出現(xiàn)過(guò)增廣鏈27計(jì)算機(jī)系統(tǒng)中圖與網(wǎng)路分析第27頁(yè)6.4.4多端網(wǎng)路問(wèn)題28計(jì)算機(jī)系統(tǒng)中圖與網(wǎng)路分析第28頁(yè)6.4.5最小費(fèi)用最大流雙權(quán)網(wǎng)路：每條弧不但有容量，還有單位流量經(jīng)過(guò)費(fèi)用兩種解法：一個(gè)基于最小費(fèi)用路徑算法；一個(gè)基于可行弧集最大流算法基于最小費(fèi)用路徑算法：總是在當(dāng)前找到最小費(fèi)用路徑上增廣流；缺點(diǎn)是每次增廣后要改變弧費(fèi)用，且出現(xiàn)負(fù)權(quán)值費(fèi)用弧基于可行弧集最大流算法：從0費(fèi)用弧集開(kāi)始應(yīng)用最大流算法，然后依據(jù)計(jì)算信息提升費(fèi)用限界P，使可行弧集增大，再應(yīng)用最大流算法，直至全部弧都進(jìn)入可行弧集。這種算法是一個(gè)主-對(duì)偶規(guī)劃解法。使用這種方法還有運(yùn)輸問(wèn)題、匹配問(wèn)題29計(jì)算機(jī)系統(tǒng)中圖與網(wǎng)路分析第29頁(yè)6.4.5以最短路為基礎(chǔ)匯總網(wǎng)路上流在電路網(wǎng)中每?jī)牲c(diǎn)之間都有中繼電路群需求，但并不是任兩點(diǎn)都有物理傳輸鏈路依據(jù)兩點(diǎn)間最短傳輸路徑將該兩點(diǎn)間電路需求量加載到這條傳輸路徑上去：設(shè)a25=10是節(jié)點(diǎn)2和5之間電路需求，節(jié)點(diǎn)2和5之間最短傳輸路徑為2

1

3

5，則加載過(guò)程為:T21=T21+10,T13=T13+10,T35=T35+10；Tij

是傳輸鏈路i

j上加載電路數(shù)；當(dāng)全部點(diǎn)間電路都加載完則算法結(jié)束30計(jì)算機(jī)系統(tǒng)中圖與網(wǎng)路分析第30頁(yè)6.5歐拉回路和中國(guó)郵遞員問(wèn)題中國(guó)郵遞員問(wèn)題(ChinesePostmanProblem,CPP)是由我國(guó)管梅谷教授于1962年首先提出并發(fā)表問(wèn)題是從郵局出發(fā)，走遍郵區(qū)全部街道最少一次再回到郵局，走什么路由才能使總旅程最短？假如街區(qū)圖是一個(gè)偶圖，依據(jù)定理3，一定有歐拉回路，CPP問(wèn)題也就迎刃而解了若街區(qū)圖不是偶圖，則必定有一些街道要被重復(fù)走過(guò)才能回到原出發(fā)點(diǎn)顯然要在奇次點(diǎn)間加重復(fù)邊怎樣使所加邊長(zhǎng)度最少歸結(jié)為求奇次點(diǎn)間最小匹配(minimumweightedmatch)—由Edmons給出多項(xiàng)式算法(1965)31計(jì)算機(jī)系統(tǒng)中圖與網(wǎng)路分析第31頁(yè)

解中國(guó)郵遞員問(wèn)題步驟0、將圖中全部懸掛點(diǎn)依次摘去1、求全部奇次點(diǎn)間最短距離和最短路徑2、依據(jù)奇次點(diǎn)間最短距離求最小完全匹配3、依據(jù)最小完全匹配和最短路徑添加重復(fù)邊4、將懸掛點(diǎn)逐一恢復(fù)，并加重復(fù)邊5、依據(jù)得到偶圖，給出歐拉回路若干種走法32計(jì)算機(jī)系統(tǒng)中圖與網(wǎng)路分析第32頁(yè)

解中國(guó)郵遞員問(wèn)題步驟33計(jì)算機(jī)系統(tǒng)中圖與網(wǎng)路分析第33頁(yè)6.6哈密爾頓回路及旅行推銷員問(wèn)題

6.6.1哈密爾頓回路(Hamiltoniancircuit)連通圖G(V,E)中回路稱為哈密爾頓回路，若該回路包含圖中全部點(diǎn)。顯然哈密爾頓回路有且只有n條邊，若|V|=n連通圖含有哈密爾頓回路充分必要條件是什么？這個(gè)問(wèn)題是由愛(ài)爾蘭數(shù)學(xué)家哈密爾頓1859年提出，但至今仍未處理歐拉回路是對(duì)邊進(jìn)行訪問(wèn)問(wèn)題，哈密爾頓回路是對(duì)點(diǎn)進(jìn)行訪問(wèn)問(wèn)題搜索哈密爾頓回路難度是NP-complete任兩點(diǎn)間都有邊圖稱為完全圖(或全連接圖)完全圖中有多少個(gè)不一樣哈密爾頓回路？完全圖中有多少個(gè)邊不相交哈密爾頓回路？最小哈密爾頓回路問(wèn)題(NP-complete)哈密爾頓路徑：包含圖中全部點(diǎn)路徑為何說(shuō)找兩點(diǎn)間最長(zhǎng)路是非常困難問(wèn)題？(n

1)!/2(n

1)/234計(jì)算機(jī)系統(tǒng)中圖與網(wǎng)路分析第34頁(yè)6.6.2旅行推銷員問(wèn)題(TravelingSalesman

Problem)旅行推銷員問(wèn)題(TSP)：設(shè)v1,v2,...,vn為n個(gè)已知城市，城市之間旅程也是已知，要求推銷員從v1出發(fā)，走遍全部城市一次且僅一次又回到出發(fā)點(diǎn)，并使總旅程最短這種不允許點(diǎn)重復(fù)旅行推銷員問(wèn)題就是最小哈密爾頓回路問(wèn)題普通旅行推銷員問(wèn)題(GTSP)：允許點(diǎn)重復(fù)TSP當(dāng)網(wǎng)路邊權(quán)滿足三角不等式時(shí)，普通旅行推銷員問(wèn)題就等價(jià)于最小哈密爾頓回路問(wèn)題當(dāng)網(wǎng)路邊權(quán)不滿足三角不等式時(shí)，只要用兩點(diǎn)間最短路距離代替原來(lái)邊權(quán)，就能夠滿足三角不等式，在此基礎(chǔ)上求最小哈密爾頓回路

經(jīng)典應(yīng)用：鄉(xiāng)郵員投遞路線郵遞員開(kāi)郵箱取信路線問(wèn)題郵車到各支局轉(zhuǎn)趟問(wèn)題35計(jì)算機(jī)系統(tǒng)中圖與網(wǎng)路分析第35頁(yè)

TSP啟發(fā)式算法(Heuristicalgorithm)窮舉法：指數(shù)算法分支定界法：隱枚舉法二交換法(two-option,Lin’salgorithm)哈密爾頓回路能夠用點(diǎn)序列表示從任一個(gè)哈密爾頓回路(即任何一個(gè)序列)出發(fā)按照一定次序試圖交換相鄰兩個(gè)點(diǎn)次序，若旅程降低則完成交換，繼續(xù)下一個(gè)交換；若沒(méi)有改進(jìn)，則不進(jìn)行此次交換，嘗試下一個(gè)交換；若全部相臨交換都試過(guò)而不能改進(jìn)，則算法結(jié)束，得到一個(gè)局部最優(yōu)點(diǎn)模擬退火(SimulatedAnnealing)隨機(jī)地采取二交換法當(dāng)交換后沒(méi)有使目標(biāo)函數(shù)改進(jìn)，也可能以玻爾茲曼分布概率被接收，但這種概率是隨模擬溫度下降而降低發(fā)揮了計(jì)算機(jī)優(yōu)點(diǎn)，盡可能降低陷入局部極值點(diǎn)模擬物理機(jī)制36計(jì)算機(jī)系統(tǒng)中圖與網(wǎng)路分析第36頁(yè)二交換法舉例初始解：1-2-3-4-5

1-3-2-4-51-3-2-4-5

1-3-4-2-51-3-4-2-5

1-3-4-5-2

5-3-4-2-13-1-4-2-537計(jì)算機(jī)系統(tǒng)中圖與網(wǎng)路分析第37頁(yè)算法復(fù)雜度Prim算法i=1n

1次比較，最多n

1次賦值i=22(n

2)次比較，最多2(n

2)次賦值i=k

k(n

k)次比較，最多k(n

k)次賦值Dijkstra算法i=1n

1次暫時(shí)標(biāo)識(shí)，永久標(biāo)識(shí)n

1次比較和賦值i=2n

2次暫時(shí)標(biāo)識(shí)，永久標(biāo)識(shí)n

2次比較和賦值i=k

n

k次暫時(shí)標(biāo)識(shí)，永久標(biāo)識(shí)n

k

次比較和賦值38計(jì)算機(jī)系統(tǒng)中圖與網(wǎng)路分析第38頁(yè)P(yáng)rim算法改進(jìn)增加一個(gè)輔助統(tǒng)計(jì)型數(shù)組，用以統(tǒng)計(jì)當(dāng)前V中各節(jié)點(diǎn)到V最小邊，minedge[i].cost統(tǒng)計(jì)該邊權(quán)值，minedge[i].vex統(tǒng)計(jì)該邊V中頂點(diǎn)。若minedge[i].cost<0則表明i

點(diǎn)進(jìn)入集合Vfori:=2tondobeginminedge[i].vex:=1;minedge[i].cost:=w[1,i]end;fori:=1ton

1dobeginmi:=maxint;forj:=2tondoif(minedge[j].cost>0)and(minedge[j].cost<mi)thenbegink:=j;mi:=minedge[j].costend;minedge[k].cost:=

minedge[k].cost;{找到k，將k加入集合V}forj:=2tondoif(w[k,j]<minedge[j].cost)thenbeginminedge[j].cost:=w[k,j];minedge[j].vex:=k;end;end;{該算法復(fù)雜度約為5n(n-1)}39計(jì)算機(jī)系統(tǒng)中圖與網(wǎng)路分析第39頁(yè)匹配問(wèn)題(MatchingProblem)定義：圖中一組邊集合，當(dāng)圖中每個(gè)節(jié)點(diǎn)最多只與該集合中一條邊相關(guān)聯(lián)，則該邊集就成為匹配。1、兩部圖匹配問(wèn)題圖中節(jié)點(diǎn)可分為兩個(gè)集合，X,Y，X與Y之間有邊相連，但X內(nèi)部和Y內(nèi)部無(wú)關(guān)聯(lián)邊，稱為兩部圖運(yùn)輸問(wèn)題實(shí)際上是兩部圖最小費(fèi)用最大流問(wèn)題任務(wù)分配問(wèn)題實(shí)際上是兩部圖最小完全匹配問(wèn)題2、非兩部圖匹配問(wèn)題(1)最大基數(shù)匹配(maximumcardinalitymatching)(2)最大權(quán)匹配(maximumweightmatching)(3)最小完全匹配(minimumweightperfectmatching)(4)最優(yōu)分?jǐn)?shù)匹配(optimalfr