第七章 圖與網(wǎng)絡(luò)分析模型選講

1、第七章第七章 圖與網(wǎng)絡(luò)分析模型選講圖與網(wǎng)絡(luò)分析模型選講一、圖論的基本知識一、圖論的基本知識1.圖的概念圖的概念定義定義 圖圖G(V,E)是指一個二元組是指一個二元組(V(G),E(G)，其中，其中: (1)V(G)=v1,v2, vn是非空有限集，稱為是非空有限集，稱為頂頂點集點集，(2)E(G)是是V(G)中的元素對中的元素對(vi,vj)組成的集合組成的集合稱為稱為邊集邊集。 圖圖G： V(G)=v1,v2,v3,v4E(G)= e1,e2,e3,e4,e5,e6e3=(v1,v3)1若圖若圖G的邊是有方向的，稱的邊是有方向的，稱G是有向圖，有向圖的邊是有向圖，有向圖的邊稱為有向邊或弧。稱

2、為有向邊或弧。常用術(shù)語常用術(shù)語 邊和它的兩端點稱為互相邊和它的兩端點稱為互相關(guān)聯(lián)關(guān)聯(lián). 與同一條邊關(guān)聯(lián)的兩個端點稱與同一條邊關(guān)聯(lián)的兩個端點稱為為相鄰相鄰的頂點，與同一個頂點的頂點，與同一個頂點點關(guān)聯(lián)的兩條邊稱為點關(guān)聯(lián)的兩條邊稱為相鄰相鄰的邊的邊.3)端點重合為一點的邊稱為端點重合為一點的邊稱為環(huán)環(huán).4) 若一對頂點之間有兩條以上的邊聯(lián)結(jié)，則這些邊若一對頂點之間有兩條以上的邊聯(lián)結(jié)，則這些邊稱為稱為重邊重邊5)既沒有環(huán)也沒有重邊的圖，稱為既沒有環(huán)也沒有重邊的圖，稱為簡單圖簡單圖 v1v2v3v4v5e1e2e3e4e5e626) 若圖若圖G的每一條邊的每一條邊e 都賦以一個實數(shù)都賦以一個實數(shù)w(e

3、)，稱稱w(e)為邊為邊e的的權(quán)權(quán)，G連同邊上的權(quán)稱為連同邊上的權(quán)稱為賦權(quán)圖賦權(quán)圖 ,記為：記為：G(V,E,W)， W=w(e)| eEv1v2v3v45327) 圖圖G的中頂點的個數(shù)，的中頂點的個數(shù)， 稱為圖稱為圖G的階；圖中與某的階；圖中與某個頂點相關(guān)聯(lián)的邊的數(shù)目，個頂點相關(guān)聯(lián)的邊的數(shù)目，稱為該頂點的度。稱為該頂點的度。8）完全圖：若無向圖的任）完全圖：若無向圖的任意兩個頂點之間都存在著意兩個頂點之間都存在著一條邊，稱此圖為完全圖。一條邊，稱此圖為完全圖。32.圖的矩陣表示圖的矩陣表示鄰接矩陣鄰接矩陣: (以下均假設(shè)圖為簡單圖以下均假設(shè)圖為簡單圖). 圖圖G的鄰接矩陣是表示頂點之間相鄰關(guān)

4、系的矩陣：的鄰接矩陣是表示頂點之間相鄰關(guān)系的矩陣： A=(aij)， 01ija若若vi與與vj相鄰相鄰若若vi與與vj不相鄰不相鄰或權(quán)值，或權(quán)值，或或，其中：其中：4v1v2v3v4 0010001111010110Av1v2v3v45431 040314305150A無向圖無向圖G鄰接矩陣鄰接矩陣A=(aij)5有向圖有向圖G鄰接矩陣鄰接矩陣A=(aij)v1v2v3v4v1v2v3v45431 0000001110000010A 00314050A6二、最大流問題二、最大流問題定義：設(shè)定義：設(shè)G(V,E)為有向圖，若在每條邊為有向圖，若在每條邊e上定義一個非上定義一個非負(fù)權(quán)負(fù)權(quán)c，則稱圖

5、，則稱圖G為一個網(wǎng)絡(luò)，稱為一個網(wǎng)絡(luò)，稱c為邊為邊e的容量函數(shù)，的容量函數(shù)，記為記為c(e)。若在有向圖若在有向圖G(V,E)中有兩個不同的頂點中有兩個不同的頂點vs與與vt ，若頂點若頂點vs只有出度沒有入度，稱只有出度沒有入度，稱vs為圖為圖G的源，的源，若頂點若頂點vt只有入度沒有出度，稱為只有入度沒有出度，稱為G的匯，的匯，若頂點若頂點v 既不是源也不是匯，稱為既不是源也不是匯，稱為v中間頂點。中間頂點。v2v4v1v3vsvt483757377v2v4v1v3vsvt48375737設(shè)設(shè)u,v網(wǎng)絡(luò)網(wǎng)絡(luò)G(V,E)的相鄰頂點，邊的相鄰頂點，邊(u,v)上的函數(shù)上的函數(shù)f(u,v)稱為邊稱

6、為邊(u,v)上的實際流量；上的實際流量；若對網(wǎng)絡(luò)若對網(wǎng)絡(luò)G(V,E)的任意相鄰頂點的任意相鄰頂點u,v 均成立：均成立： 0 f(u,v) c(u,v) ， 稱該網(wǎng)絡(luò)為相容網(wǎng)絡(luò)。稱該網(wǎng)絡(luò)為相容網(wǎng)絡(luò)。若若v為網(wǎng)絡(luò)為網(wǎng)絡(luò)G(V,E)的中間頂點，的中間頂點， Vuvuf),( Vwwvf),(有：有：8v2v4v1v3vsvt48375737網(wǎng)絡(luò)的總流量為從源網(wǎng)絡(luò)的總流量為從源vs 流出的總流量：流出的總流量： VwswvffV),()(流入?yún)R流入?yún)Rvt 總流量：總流量： VutvuffV),()(9設(shè)網(wǎng)絡(luò)設(shè)網(wǎng)絡(luò)G(V,E,C)，其中，其中 為源為源 ， 為匯，為匯，),(ijcC svtv為邊為

7、邊 上的容量，上的容量，ijc),(jivv若流若流 滿足：滿足：ijff （1）容量限制條件：）容量限制條件：對每一條弧對每一條弧 成立成立Evvji ),(ijijcf 0（2）平衡條件：）平衡條件： Vuuvf),( Vuvuf),( ttssvvfVvvvvvfV),(, 0),(稱流稱流 為可行流，為可行流，V( f )為總流量。為總流量。ijff 10 若存在一個可行流若存在一個可行流f *，使得對所有可行流，使得對所有可行流 f 都有都有V(f *) V(f )成立，則稱成立，則稱f *為最大流。為最大流。11最大流模型：最大流模型：)(maxfVs.t: VvijVvjijjv

8、vfvvf),(),(,),(0ijjicvvf ),(Vvvji sivvfV ),(tsivvv, 0 tvvfV ),(例例7.1分組交換技術(shù)在計算機網(wǎng)絡(luò)中發(fā)揮著重要作用，信分組交換技術(shù)在計算機網(wǎng)絡(luò)中發(fā)揮著重要作用，信息從源節(jié)點到目的節(jié)點不再需要一條固定的路徑，而是息從源節(jié)點到目的節(jié)點不再需要一條固定的路徑，而是將其分割為幾組，通過不同的路徑傳輸?shù)侥康墓?jié)點，目將其分割為幾組，通過不同的路徑傳輸?shù)侥康墓?jié)點，目的節(jié)點再重新組合還原文件。現(xiàn)考察如圖所示的網(wǎng)絡(luò)，的節(jié)點再重新組合還原文件?，F(xiàn)考察如圖所示的網(wǎng)絡(luò)，圖中兩節(jié)點間的數(shù)字表示兩交換機間可用的帶寬，此時圖中兩節(jié)點間的數(shù)字表示兩交換機間可用的帶

9、寬，此時從節(jié)點從節(jié)點1到節(jié)點到節(jié)點9的最大帶寬為多少？的最大帶寬為多少？v2v5v1v3v82.5v9v4v7v67.13.46.15.62.43.63.87.44.95.77.25.34.53.86.77.412設(shè)設(shè)fij為從為從vi到到vj的實際流量，得一個的實際流量，得一個9階方陣：階方陣：F=( fij)記容量矩陣為記容量矩陣為C =0 2.5 0 5.6 6.1 0 0 0 00 0 7.1 0 0 3.6 0 0 00 0 0 0 0 0 0 3.4 00 0 0 0 4.9 0 7.4 0 00 2.4 0 0 0 7.2 5.7 0 00 0 3.8 0 0 0 0 5.3 4

10、.50 0 0 0 0 3.8 0 0 6.70 0 0 0 0 0 0 0 7.40 0 0 0 0 0 0 0 0 v2v5v1v3v82.5v9v4v7v67.13.46.15.62.43.63.87.44.95.77.25.34.53.86.77.413sets: node/v1.v9/;arc(node,node):c,f;endsetsOBJmax=flow;for(node(i)|i#ne#1#and#i#ne#9:sum(node(j):f(i,j)=sum(node(j):f(j,i);sum(node(j): f(1,j)=flow;sum(node(j): f(j,9)=

11、flow;for(arc:bnd(0,f,c);)(maxfV VujiVuijjjff 9 ),(9 , 1 , 01 ),(ifViifV,0CF .ts14data:c=0 2.5 0 5.6 6.1 0 0 0 00 0 7.1 0 0 3.6 0 0 00 0 0 0 0 0 0 3.4 00 0 0 0 4.9 0 7.4 0 00 2.4 0 0 0 7.2 5.7 0 00 0 3.8 0 0 0 0 5.3 4.50 0 0 0 0 3.8 0 0 6.70 0 0 0 0 0 0 0 7.40 0 0 0 0 0 0 0 0;text()=table(f);enddata1

12、5 Objective value: 14.20000 V1 V2 V3 V4 V5 V6 V7 V8 V9 V1 0 2.5 0 5.6 6.1 0 0 0 0 V2 0 0 3.4 0 0 1.5 0 0 0 V3 0 0 0 0 0 0 0 3.4 0 V4 0 0 0 0 3.3 0 2.3 0 0 V5 0 2.4 0 0 0 7 0 0 0 V6 0 0 0 0 0 0 0 4 4.5 V7 0 0 0 0 0 0 0 0 2.3 V8 0 0 0 0 0 0 0 0 7.4 V9 0 0 0 0 0 0 0 0 0v2v5v1v3v82.5v9v4v7v67.13.46.15.6

13、2.43.63.87.44.95.77.25.34.53.86.77.416例例7.2 （最小費用最大流）在如圖所示的運輸網(wǎng)絡(luò)中，（最小費用最大流）在如圖所示的運輸網(wǎng)絡(luò)中，從從 發(fā)送物資到發(fā)送物資到 ，圖中邊上括號里的第一個數(shù)字代，圖中邊上括號里的第一個數(shù)字代表路段上該物資的單位運輸成本，第表路段上該物資的單位運輸成本，第2個數(shù)字代表路個數(shù)字代表路段的實際通行能力，問如何組織運輸可以獲得成本最段的實際通行能力，問如何組織運輸可以獲得成本最低的最大運輸量。低的最大運輸量。svtv17:ijc節(jié)點節(jié)點 到到 的單位運輸成本，得矩陣的單位運輸成本，得矩陣ivjv nnijcC :ijd邊邊 上的容量

14、，得容量矩陣上的容量，得容量矩陣),(jivv nnijdD 決策變量：邊決策變量：邊 上的流量上的流量 ，得流量矩陣，得流量矩陣),(jivv nnijff 要求流量最大和成本最小，可建立多目標(biāo)規(guī)劃模型。要求流量最大和成本最小，可建立多目標(biāo)規(guī)劃模型。流量最大：流量最大：)(maxfV成本最?。撼杀咀钚。?ninjijijfc11min約束條件：約束條件： VujiVuijjjff sivvfV ),(tsivvv, 0 tvvfV ),(ijijdf 0ijf18模型求解：（分兩步完成）模型求解：（分兩步完成）第一步：先求解第一目標(biāo)第一步：先求解第一目標(biāo))(maxfV VujiVuijjjf

15、f sivvfV ),(tsivvv, 0 tvvfV ),(ijijdf 019)(maxfV VujiVuijjjff sivvfV ),(tsivvv, 0 tvvfV ),(ijijdf 0 sets: node/s,1,2,3,4,5,6,7,t/; arc(node,node):d,f; endsets OBJmax=flow;for(node(i)|i#ne#1#and#i#ne#9:sum(node(j):f(i,j)=sum(node(j):f(j,i);sum(node(j): f(1,j)=flow;sum(node(j): f(j,9)=flow;for(arc:bnd

16、(0,f,d);20data: d= 0, 60, 30, 50, 0, 0, 0, 0, 0, 0, 0, 0, 0, 45, 30, 0, 0, 0, 0, 0, 0, 0, 0, 30, 25, 0, 0, 0, 0, 20, 0, 0, 0, 30, 0, 0, 0, 0, 0, 0, 0, 35, 0, 30,30, 0, 0, 0, 0, 0, 0, 0, 40,50, 0, 0, 0, 0, 0, 0, 0, 0, 40, 0, 0, 0, 0, 0, 0, 0, 0, 20, 0, 0, 0, 0, 0, 0, 0, 0, 0;text()=table(f);enddata21

17、 Objective value: 130.0000 S 1 2 3 4 5 6 7 T S 0 60 20 50 0 0 0 0 0 1 0 0 0 0 45 15 0 0 0 2 0 0 0 0 0 30 10 0 0 3 0 0 20 0 0 0 30 0 0 4 0 0 0 0 0 0 0 15 30 5 0 0 0 0 0 0 0 5 40 6 0 0 0 0 0 0 0 0 40 7 0 0 0 0 0 0 0 0 20 T 0 0 0 0 0 0 0 0 0最大流量：最大流量：f=13022將最優(yōu)值加入約束，求第二目標(biāo)：將最優(yōu)值加入約束，求第二目標(biāo)： ninjijijfc11mi

18、n VujiVuijjjff sivv ,130tsivvv, 0 tvv ,130ijijdf 0 sets: node/s,1,2,3,4,5,6,7,t/; arc(node,node):c,d,f; endsets OBJmin=sum(arc:c*f);for(node(i)|i#ne#1#and#i#ne#9:sum(node(j):f(i,j)=sum(node(j):f(j,i);sum(node(j): f(1,j)=flow;sum(node(j): f(j,9)=flow;for(arc:bnd(0,f,d);23data: flow=130;d= 0, 60, 30,

19、50, 0, 0, 0, 0, 0, 0, 0, 0, 0, 45, 30, 0, 0, 0, 0, 0, 0, 0, 0, 30, 25, 0, 0, 0, 0, 20, 0, 0, 0, 30, 0, 0, 0, 0, 0, 0, 0, 35, 0, 30,30, 0, 0, 0, 0, 0, 0, 0, 40,50, 0, 0, 0, 0, 0, 0, 0, 0, 40, 0, 0, 0, 0, 0, 0, 0, 0, 20, 0, 0, 0, 0, 0, 0, 0, 0, 0;c=0, 4, 5, 3, 0, 0, 0, 0, 0, 0, 0, 0, 0, 5, 3, 0, 0, 0,

20、 0, 0, 0, 0, 0, 3, 2, 0, 0, 0, 0, 2, 0, 0, 0, 4, 0, 0,0, 0, 0, 0, 0, 5, 0, 3, 4, 0, 0, 0, 0, 0, 0, 0, 4, 3, 0, 0, 0, 0, 0, 0, 0, 0, 4, 0, 0, 0, 0, 0, 0, 0, 0, 4,0, 0, 0, 0, 0, 0, 0, 0, 0;text()=table(f);enddata24Objective value: 1510.000 S 1 2 3 4 5 6 7 T S 0 60 30 40 0 0 0 0 0 1 0 0 0 0 30 30 0 0 0

21、 2 0 0 0 0 0 30 20 0 0 3 0 0 20 0 0 0 20 0 0 4 0 0 0 0 0 0 0 0 30 5 0 0 0 0 0 0 0 10 50 6 0 0 0 0 0 0 0 0 40 7 0 0 0 0 0 0 0 0 10 T 0 0 0 0 0 0 0 0 025定義定義1 在圖在圖G(V,E)中，若頂點中，若頂點 與邊與邊ei相互關(guān)聯(lián)，相互關(guān)聯(lián)，iivv,1 稱非空序列稱非空序列12110kkkvevevevw ), 2 , 1(ki 為從為從v0到到vk的一條的一條通路通路，邊不重復(fù)但頂點可重復(fù)的通路稱為邊不重復(fù)但頂點可重復(fù)的通路稱為道路道路，邊與頂點

22、均不重復(fù)的通路稱為邊與頂點均不重復(fù)的通路稱為路徑路徑。44112544141vevevevevwvv 通路：通路：4521141vevevPvv 道路：道路：4332264521141vevevevevevTvv 路徑：路徑：三、最短路三、最短路問題問題26路徑路徑 ，則稱則稱 為路徑為路徑P的權(quán)的權(quán)定義定義2 (1) 任意兩點均有路徑的圖稱為連通圖任意兩點均有路徑的圖稱為連通圖(2) 起點與終點重合的路徑稱為圈起點與終點重合的路徑稱為圈(3) 連通而無圈的圖稱為樹連通而無圈的圖稱為樹定義定義3 (1) 設(shè)設(shè)P(u,v) 是賦權(quán)圖是賦權(quán)圖G中從頂點中從頂點u到頂點到頂點v )()()(PEee

23、wPw(2)在賦權(quán)圖在賦權(quán)圖G中，從頂點中，從頂點u到頂點到頂點v具有最小權(quán)的具有最小權(quán)的路徑路徑 ，稱為，稱為u到到v最短路最短路。27指定頂點到其余頂點的最短路算法：指定頂點到其余頂點的最短路算法： Dijkstra算法算法 在在matlab中使用命令中使用命令graphshortestpath實現(xiàn)。實現(xiàn)。調(diào)用格式：調(diào)用格式：dist,path=graphshortestpath(DG,A,B) dist： A與與B之間的最短路的長度之間的最短路的長度 path： A與與B之間的最短路的路徑之間的最短路的路徑 DG：權(quán)數(shù)鄰接矩陣：權(quán)數(shù)鄰接矩陣28例例7.3 某地某地10個點個點v1,v2,

24、v10間的道路連接情況為：間的道路連接情況為：相鄰點相鄰點 距離距離 相鄰點相鄰點 距離距離 相鄰點相鄰點 距離距離 相鄰點相鄰點 距離距離12: 4.2， 13: 5.6， 14: 6.5 23: 3.5， 25: 6.5， 27: 15.2 34: 3.8， 35: 5.4， 36: 7.645: 5.1 ， 46: 5.1， 47: 8.8， 48: 12.356: 4.7 ， 57: 5.2， 59: 7.667: 6.3， 68: 3.9， 69: 5.278: 6.9， 79: 3.5， 710: 6.389: 6.8， 810: 5.9，910: 5.8 求由求由v1到到v10間

25、的最短路。間的最短路。29(程序程序li703)clc,clearx=1:8,1:8,1:7,9,4,10;y=2:9,3,5,5:10,4,7,6,7,9,9,10,10,8,10; w=4.2,3.5,3.8,5.1,4.7,6.3,6.9,6.8,5.6,6.5,5.4,5.1,5.2,3.9,3.5,5.9,6.5,15.2,7.6,8.8,7.6,5.2,6.3,5.8,12.3,0;相鄰點相鄰點 距離距離 相鄰點相鄰點 距離距離 相鄰點相鄰點 距離距離 相鄰點相鄰點 距離距離12: 4.2， 13: 5.6， 14: 6.5 23: 3.5， 25: 6.5， 27: 15.2 3

26、4: 3.8， 35: 5.4， 36: 7.645: 5.1 ， 46: 5.1， 47: 8.8， 48: 12.356: 4.7 ， 57: 5.2， 59: 7.667: 6.3， 68: 3.9， 69: 5.278: 6.9， 79: 3.5， 710: 6.389: 6.8， 810: 5.9，910: 5.8 30W=sparse(x,y,w);B=W+W;dist,path=graphshortestpath(B,1,10)ids=v1,v2,v3,v4,v5,v6,v7,v8,v9,v10;bg=biograph(W,ids,ShowArrows,off,ShowWeigh

27、ts,on)h=view(bg)set(h.Nodes(path),Color,1,0.5,0.5)edges=getedgesbynodeid(h,get(h.Nodes(path),ID);set(edges,LineColor,0,1,0)set(edges,LineWidth,2) 31 4.2 5.6 6.5 3.5 6.5 15.2 3.8 5.4 7.6 5.1 5.1 8.8 12.3 4.7 5.2 7.6 6.3 3.9 5.2 6.9 3.5 6.3 6.8 5.9 5.8 v1v2v3v4v5v6v7v8v9v10dist = 21.4000path = 1 4 6 8

28、 1032每對頂點之間的最短路：每對頂點之間的最短路： floyd算法：算法：設(shè)圖設(shè)圖G(V,E,W)的權(quán)鄰接矩陣為：的權(quán)鄰接矩陣為：其中其中 當(dāng)當(dāng)vi與與vj之間沒有邊相連時，取之間沒有邊相連時，取 當(dāng)當(dāng)vi與與vj之間有邊時，取之間有邊時，取 wij 為該邊的權(quán)。為該邊的權(quán)。對于無向圖對于無向圖G，鄰接矩陣，鄰接矩陣D0是對稱矩陣。是對稱矩陣。 nnijdD )()0(0)0(ijd )0(ijd，ijijwd )0(33(3)遞推產(chǎn)生一個矩陣序列遞推產(chǎn)生一個矩陣序列D0, D1, Dn(4) 為最短路距離矩陣，為最短路距離矩陣，floyd算法的步驟：算法的步驟：（求有（求有n個節(jié)點的圖的

29、最短路距離矩陣個節(jié)點的圖的最短路距離矩陣Dn的步驟）的步驟）(1)初值初值k=0，nnijdD )()(00 0nnnijndD )()()(nijd為為vi到到vj的最短路的距離。的最短路的距離。(2)計算計算,min)1()1()1()( kkjkikkijkijdddd34建立最短路徑矩陣建立最短路徑矩陣R的步驟：的步驟：（1） ,)()0()0(nnijrR jrij )0( , )2()1()(kijkijrkr(1)(1)(1)kkkijikkjddd (1)(1)(1)kkkijikkjddd (3)遞推產(chǎn)生一個矩陣序列遞推產(chǎn)生一個矩陣序列R0,R1,Rn(4)矩陣矩陣R=Rn為

30、最短路徑矩陣為最短路徑矩陣35查找最短路路徑的方法：查找最短路路徑的方法：若若 則則 是是點點vi與到點與到點vj最短路徑的途中點，最短路徑的途中點，1)(arnij 1av(1) 向起點向起點vi與追溯：與追溯：，1)(arnij ，2)(1arnia ， 3)(2arnia ( )kniakra 得：得：12,aaaivvvvk(2) 向終點向終點vj與追溯：與追溯：，1)(arnij ，1)(1brnja ,2)(1，brnjb ，jrnjbm )(得：得：jbbbavvvvvm,211(3)點點vi與到點與到點vj最短路路徑：最短路路徑：jbbbaaaivvvvvvvvmk,21123

31、6建立由建立由floyd算法求最短路長矩陣的算法求最短路長矩陣的matlab函數(shù)：函數(shù)：function D=zuiduan(B) n=length(B); D=B; for k=1:n for i=1:n for j=1:n if D(i,k)+D(k,j)D(i,j) D(i,j)=D(i,k)+D(k,j); end end endendD=full(D); 37例例7.4某城市要建立一個消防站，為該市所屬的九個區(qū)服務(wù)，某城市要建立一個消防站，為該市所屬的九個區(qū)服務(wù)，如圖所示問應(yīng)設(shè)在哪個區(qū)，才能使它至最遠(yuǎn)區(qū)的路徑最短？如圖所示問應(yīng)設(shè)在哪個區(qū)，才能使它至最遠(yuǎn)區(qū)的路徑最短？記消防站建在記消防

32、站建在vi處的最大服務(wù)距離為處的最大服務(wù)距離為S(vi)，(i=1,2,n)模型建立：模型建立： )(min)(1inikvSvS S(vi)：vi到其它節(jié)點的最短路程的最大值。到其它節(jié)點的最短路程的最大值。記記dij為節(jié)點為節(jié)點vi到節(jié)點到節(jié)點vj的最短路程的最短路程ijnjidvS 1max)(求求dij 最短路問題！最短路問題！用用floyd算法算法12358447634637736593866838 B 0 4 4 0 3 7 3 8 3 0 4 3 0 6 7 6 7 3 6 0 3 0 5 6 5 0 8 7 6 0 6 6 6 012358447634637736593866賦權(quán)

33、鄰接矩陣：賦權(quán)鄰接矩陣：3912358447634637736593866 x=1,2,4 2,3,3 2,5,7 2,6,3 2,8,8 3,4,4 3,5,3 4,5,6 4,8,7 4,9,6 6,7,5 6,8,6 8,9,6 9,9,0 40 建立一個構(gòu)造鄰接矩陣的函數(shù)文件：建立一個構(gòu)造鄰接矩陣的函數(shù)文件： function B=qlinjie(x) a=x(:,1);b=x(:,2);c=x(:,3); B=sparse(a,b,c); B=full(B+B); B(find(B=0)=inf; for i=1:length(B) B(i,i)=0; end41clc,clear

34、x=1,2,4;2,3,3;2,5,7;2,6,3;2,8,8;3,4,4;3,5,3;4,5,6;4,8,7;4,9,6;6,7,5;6,8,6;8,9,6;9,9,0;B=fun704(x);D=zuiduan(B); %最短距離矩陣最短距離矩陣S=max(D) %最大服務(wù)距離最大服務(wù)距離k=find(S=min(S) %最佳選址點最佳選址點主程序（主程序（li704）：）：42 求解結(jié)果：求解結(jié)果： S = 17 13 11 15 14 12 17 13 17 k=3應(yīng)該在第應(yīng)該在第3個節(jié)點建消防站。個節(jié)點建消防站。43例例7.5 某礦區(qū)有某礦區(qū)有7個礦點（如圖所示）各礦點每天的產(chǎn)礦量為

35、個礦點（如圖所示）各礦點每天的產(chǎn)礦量為 )(jvq現(xiàn)要從這現(xiàn)要從這7個礦點選一個來建造礦廠問應(yīng)選在哪個礦點，才能使個礦點選一個來建造礦廠問應(yīng)選在哪個礦點，才能使各礦點所產(chǎn)的礦運到選礦廠所在地的總運量（千噸公里）最小。各礦點所產(chǎn)的礦運到選礦廠所在地的總運量（千噸公里）最小。 （1）求最短路程矩陣：）求最短路程矩陣： dij為節(jié)點為節(jié)點vi到節(jié)點到節(jié)點vj的最短路程的最短路程)(ijdD （2）計算在第）計算在第i 個礦點建礦廠的總運量：個礦點建礦廠的總運量：ijjjidvqvm )()(71 （3）求）求vk使使)(min)(71iikvmvm 44在第在第i 個礦點建礦廠的總運力：個礦點建礦廠

36、的總運力：ijjjidvqvm )()(711771221111dqdqdqm 2772222112dqdqdqm 7777227117dqdqdqm 表示為矩陣乘積：表示為矩陣乘積：TDqM 最短距離矩陣最短距離矩陣D=(dij)45clc,clear x=1,2,3;2,3,2;2,6,4;3,4,6;3,5,2;4,5,1;5,6,4;6,7,1.5;7,7,0; q=3,2,7,1,6,1,4; %各礦點日產(chǎn)量各礦點日產(chǎn)量 B=fun704(x); %權(quán)鄰接矩陣權(quán)鄰接矩陣 D=zuiduan(B); %最短距離矩陣最短距離矩陣 M=D*q %各礦點建廠的總運量各礦點建廠的總運量 k=f

37、ind(M=min(M) %最佳選址點最佳選址點主程序（主程序（li705）：）：46求解結(jié)果：求解結(jié)果： M = 132 78 70 92 70 106 130 k = 3 5應(yīng)該在第應(yīng)該在第3礦點或第礦點或第5礦點建廠。礦點建廠。47四、四、旅行推銷員問題（旅行推銷員問題（TSPTSP問題）問題） 定義定義1設(shè)設(shè)G=(V,E)是連通無向圖是連通無向圖 (1) 經(jīng)過經(jīng)過G的每邊至少一次的的每邊至少一次的閉通路閉通路稱為巡回稱為巡回 (2) 經(jīng)過經(jīng)過G的每邊正好一次的巡回稱為歐拉巡回的每邊正好一次的巡回稱為歐拉巡回 (3) 存在歐拉巡回的圖稱為歐拉圖存在歐拉巡回的圖稱為歐拉圖 (4) 經(jīng)過經(jīng)過

38、G的每邊正好一次的道路稱為歐拉道路的每邊正好一次的道路稱為歐拉道路 e3 v1 v2 v3 v4e1e2e4 e5e6 e3 v1 v2 v3 v4 e1e 2e4e5歐拉道路：歐拉道路：v1e1v2e2v3e5v1e4v4e3v3歐拉巡回：歐拉巡回：v1e1v2e2v3e5v1e4v4e3v3e6v148 定義定義2 設(shè)設(shè)G=(V,E)是連通無向圖是連通無向圖. (1) 經(jīng)過經(jīng)過G的每個頂點正好一次的路徑，的每個頂點正好一次的路徑，稱為稱為G的一條哈密爾頓路徑的一條哈密爾頓路徑 (2) 經(jīng)過經(jīng)過G的每個頂點正好一次的圈，的每個頂點正好一次的圈，稱為稱為G的哈密爾頓圈或的哈密爾頓圈或H圈圈 (

39、3) 含含H圈的圖稱為哈密爾頓圖或圈的圖稱為哈密爾頓圖或H圖圖 49旅行推銷員問題（旅行推銷員問題（TSPTSP問題）問題）: : 推銷員需要訪問某地區(qū)的所有城鎮(zhèn)，最后回到推銷員需要訪問某地區(qū)的所有城鎮(zhèn)，最后回到出發(fā)點問如何安排旅行路線使總行程最小出發(fā)點問如何安排旅行路線使總行程最小。 若用頂點表示城鎮(zhèn)，邊表示連接兩城鎮(zhèn)的路，若用頂點表示城鎮(zhèn)，邊表示連接兩城鎮(zhèn)的路，邊上的權(quán)表示距離（或時間、或費用），邊上的權(quán)表示距離（或時間、或費用），推銷員問題就成為在加權(quán)圖中尋找一條經(jīng)過每個頂推銷員問題就成為在加權(quán)圖中尋找一條經(jīng)過每個頂點至少一次的最短閉通路問題點至少一次的最短閉通路問題。定義定義3在加權(quán)圖

40、在加權(quán)圖G=(V,E)中，中， (1)權(quán)最小的哈密爾頓圈稱為最佳權(quán)最小的哈密爾頓圈稱為最佳H圈圈。 (2)經(jīng)過每個頂點至少一次的權(quán)最小的閉通路稱經(jīng)過每個頂點至少一次的權(quán)最小的閉通路稱為最佳推銷員回路為最佳推銷員回路。50 注意：最佳哈密爾頓圈不一是最佳注意：最佳哈密爾頓圈不一是最佳推銷員回路，同樣最佳推銷員回路推銷員回路，同樣最佳推銷員回路也不一定是最佳哈密爾頓圈。也不一定是最佳哈密爾頓圈。1v2v3v1120 定理定理 在加權(quán)圖在加權(quán)圖G=(V,E)中，若對任意中，若對任意,Vzyx ,yzxz 都有都有),(),(),(yzwzxwyxw 則圖則圖G的最佳的最佳H圈也是最佳推銷員回路圈也是

41、最佳推銷員回路。到目前為止，到目前為止，TSP問題還沒有有效解決方法，問題還沒有有效解決方法，現(xiàn)有的方法都是尋找近似最優(yōu)的哈密頓圈，現(xiàn)有的方法都是尋找近似最優(yōu)的哈密頓圈，常用方法有邊替換法、遺傳算法、模擬退火法、常用方法有邊替換法、遺傳算法、模擬退火法、蟻群算法等。蟻群算法等。51引入引入0-1變量：變量：xij=1，由第，由第i城市進入第城市進入第j城市，且城市，且i j0，其它，其它 目標(biāo)函數(shù)：目標(biāo)函數(shù)： niniijijxcz11min對規(guī)模不大的對規(guī)模不大的TSP問題可將其轉(zhuǎn)化為數(shù)學(xué)規(guī)劃問題：問題可將其轉(zhuǎn)化為數(shù)學(xué)規(guī)劃問題：, 11 niijx j=1,2,3,n, 11 njijx i

42、=1,2,3,n ,1 , 0 ijx i, j =1,2,3,n52123456到此得到了一個模型，它是一個指派問題的整數(shù)規(guī)到此得到了一個模型，它是一個指派問題的整數(shù)規(guī)劃模型。但以上兩個條件對于劃模型。但以上兩個條件對于TSPTSP來說并不充分，來說并不充分，僅僅是必要條件。僅僅是必要條件。例如：例如：以上兩個條件都滿足，但它顯然不是以上兩個條件都滿足，但它顯然不是TSPTSP的解，的解，它存在兩個子巡回。它存在兩個子巡回。則可以避免產(chǎn)生子巡回。則可以避免產(chǎn)生子巡回。若在原模型上添加變量若在原模型上添加變量ui ，并附加下面形式的約束條件：并附加下面形式的約束條件：，1 nnxuuijji.

43、 12 nji, 20 nui53引入引入0-1變量：變量：xij=1，由第，由第i城鎮(zhèn)進入第城鎮(zhèn)進入第j城鎮(zhèn)，且城鎮(zhèn)，且i j0，其它，其它 對規(guī)模不大的對規(guī)模不大的TSP問題可將其轉(zhuǎn)化為數(shù)學(xué)規(guī)劃問題：問題可將其轉(zhuǎn)化為數(shù)學(xué)規(guī)劃問題：目標(biāo)函數(shù)：目標(biāo)函數(shù)： niniijijxcz11min s.t：, 11 niijx, 11 njijx, 1 nnxuuijji,2nji , 20 nui i=2,3,n, 1 , 0 ijx i,j=1,2,3,n j=1,2,3,n i=1,2,3,n54例例7. 6 (TSP問題問題) 已知已知9個城市間的旅行費用（見表）個城市間的旅行費用（見表）問他應(yīng)

44、按怎樣的次序訪問這些城市，能使得總旅費最問他應(yīng)按怎樣的次序訪問這些城市，能使得總旅費最少？少？ 0, 3.1, 5.2, 4.3, 5.2, 6.5, 8.8, 7.3, 5.9, 3.1, 0, 4.8, 8.1, 9.3, 8.7, 6.4, 4.5, 7.2, 5.2, 4.8, 0, 7.7, 9.5, 4.9, 5.3, 6.6, 6.8, 4.3, 8.1, 7.7, 0, 7.3, 11.2, 10.8,9.7, 8.8, 5.2, 9.3, 9.5, 7.3, 0, 10.5, 11.3,7.9, 9.4, 6.5, 8.8, 4.9, 11.2,10.5, 0, 6.1, 5

45、.8, 7.5, 8.8, 6.4, 5.3, 10.8,11.3, 6.1, 0, 6.6, 4.9, 7.3, 4.5, 6.6, 9.7, 7.9, 5.8, 6.6, 0, 5.8, 5.9, 7.2, 6.8, 8.8, 9.4, 7.5, 4.9, 5.8, 0;城市編號城市編號 1 2 3 4 5 6 7 8 91 2 3 4 5 6 7 8 955 9191miniiijijxcz s.t：, 191 iijx, 191 jijx, 89 ijjixuu, 70 iu, 1 , 0 ijx , ji ),92( ji, ji i,j=1,2,3,nsets: city /1.9

46、/:u; link(city,city):c,x; endsets OBJmin=sum(link:c*x); for(city(j):sum(city(i)|i#ne#j:x(i,j)=1);for(city(i):sum(city(j)|j#ne#i:x(i,j)=1); for(city(i)|i#gt#1:for(city(j)|j#gt#1#and#i#ne#j: u(i)-u(j)+9*x(i,j)=8); for(city(i)|i#gt#1:u(I)=0);for(link:bin(x);56data: c=0, 3.1, 5.2, 4.3, 5.2, 6.5, 8.8, 7.

47、3, 5.9, 3.1, 0, 4.8, 8.1, 9.3, 8.7, 6.4, 4.5, 7.2, 5.2, 4.8, 0, 7.7, 9.5, 4.9, 5.3, 6.6, 6.8, 4.3, 8.1, 7.7, 0, 7.3, 11.2, 10.8,9.7, 8.8, 5.2, 9.3, 9.5, 7.3, 0, 10.5, 11.3,7.9, 9.4, 6.5, 8.8, 4.9, 11.2,10.5, 0, 6.1, 5.8, 7.5, 8.8, 6.4, 5.3, 10.8,11.3, 6.1, 0, 6.6, 4.9, 7.3, 4.5, 6.6, 9.7, 7.9, 5.8,

48、6.6, 0, 5.8, 5.9, 7.2, 6.8, 8.8, 9.4, 7.5, 4.9, 5.8, 0;enddata57Objective value: 49.10000X( 1, 4) 1.000000X( 2, 1) 1.000000 X( 3, 2) 1.000000X( 4, 5) 1.000000 X( 5, 8) 1.000000 X( 6, 3) 1.000000 X( 7, 6) 1.000000 X( 8, 9) 1.000000 X( 9, 7) 1.000000 按如下次序：按如下次序： 1,4,5,8,9,7,6,3,2,1 訪問這些城市時總訪問這些城市時總費用

49、最小，最小費費用最小，最小費用：用：49.158五、最小生成樹五、最小生成樹問題問題1v樹：樹： 連通且不含圈的無向圖稱為連通且不含圈的無向圖稱為樹樹常用常用T表示表示.樹中的邊稱為樹中的邊稱為樹枝樹枝. 樹中度為樹中度為1的頂點稱為的頂點稱為樹葉樹葉. 2v3v4v5v支撐樹：支撐樹： 設(shè)圖設(shè)圖G(V,E)，若，若T是樹，是樹，且且稱樹稱樹T是圖是圖G的支撐（生成）樹。的支撐（生成）樹。 ( )( ), ( )( )E TE G V TV G ，最小生成樹：賦權(quán)連通圖最小生成樹：賦權(quán)連通圖G的所有支撐樹中，其各邊的所有支撐樹中，其各邊權(quán)之和最小的支撐樹，稱為連通圖權(quán)之和最小的支撐樹，稱為連通

50、圖G的最小生成樹。的最小生成樹。解決最小生成樹的常用方法：克魯斯卡爾算法、普利解決最小生成樹的常用方法：克魯斯卡爾算法、普利姆算法。姆算法。59普利姆（普利姆（Prim）算法：）算法： 設(shè)置兩個集合設(shè)置兩個集合P和和Q，其中，其中P、Q分別用于存放最分別用于存放最小生成樹的頂點和邊，小生成樹的頂點和邊，P的初值為的初值為P=v1，Q的初值為的初值為Q=。 普利姆算法的基本思想：從所有普利姆算法的基本思想：從所有的邊中，選取一條具有最小權(quán)值的邊的邊中，選取一條具有最小權(quán)值的邊uv，將頂點，將頂點v加加入到集合入到集合P中，將邊中，將邊uv加入到集合加入到集合Q中，不斷重復(fù)下中，不斷重復(fù)下去，直到

51、去，直到P= =V中止。中止。PVvPu ,60普利姆（普利姆（Prim）算法：）算法： 設(shè)置兩個集合設(shè)置兩個集合T和和Q，其中，其中T、Q分別用于存放最分別用于存放最小生成樹的頂點和邊，小生成樹的頂點和邊，T的初值為的初值為T=v1，Q的初值為的初值為Q=。普利姆算法的基本思想：普利姆算法的基本思想：從所有從所有 的邊的邊uv中，中，選取一條具有最小權(quán)值的邊選取一條具有最小權(quán)值的邊uv，將頂點將頂點v加入到集合加入到集合T中，再將從集合中，再將從集合S中剔除，中剔除，將邊將邊uv加入到集合加入到集合Q中，中，不斷重復(fù)下去，直到不斷重復(fù)下去，直到T= =V中止。中止。PVSvPu ,61123

52、56465854367669764Q=v2v6Q=v2v6,v2v1Q=v2v6,v2v1,v1v3Q=v2v6,v2v1,v1v3,v3v5最生成小樹為最生成小樹為Tree=v2v6,v2v1,v1v3,v3v5,v6v7,v7v4 最小生成樹的權(quán)為最小生成樹的權(quán)為27。例例7.7 求右圖的最小生成樹求右圖的最小生成樹Q=v2v6,v2v1,v1v3,v3v5,v6v7Q=v2v6,v2v1,v1v3,v3v5,v6v7,v7v462Prim算法的算法的matlab實現(xiàn)：實現(xiàn)： function A,B,Tch=primg(w,a) %w: 權(quán)矩陣，權(quán)矩陣，a：起始點編號：起始點編號 n=l

53、ength(w); T=a; S=setdiff(1:n,T); A=;B=; L=; w(w=0)=inf; k1=1; k2=n-1;Prim算法：算法：圖圖G(V,E,W)(1)T=v1, Q= S=setdiff(V,T),(2)找頂點找頂點u與與v滿足：滿足：min ( , )|,w u vu T vS T=T,v,S=setdiff(S,v)Q =Q, uv(3)若若T=V結(jié)束循環(huán)結(jié)束循環(huán) 否則轉(zhuǎn)向否則轉(zhuǎn)向(2)63 while k1n min=inf; for m1=1:k1 for m2=1:k2 t=w(T(m1),S(m2); if tmin min=t; u=T(m1);

54、 v=S(m2); end end end T=T,v; S=setdiff(S,v); A=A,u;B=B,v; L=L,min; k1=length(T);k2=length(S); end Tch=sum(L); Prim算法：算法：圖圖G(V,E,W)(1)T=v1, Q= S=setdiff(V,T),(2)找頂點找頂點u與與v滿足：滿足：min ( , )|,w u vu T vS T=T,v,S=setdiff(S,v)Q =Q, uv(3)若若T=V結(jié)束循環(huán)結(jié)束循環(huán) 否則轉(zhuǎn)向否則轉(zhuǎn)向(2)64例例7.8某單位有某單位有10個下屬部門，均不在同一地點辦公，個下屬部門，均不在同一地點辦公，為了實現(xiàn)部門之間的資源共享，該單位打算對原有網(wǎng)絡(luò)為了實現(xiàn)部門之間的資源共享，該單位打算對原有網(wǎng)絡(luò)進行改造，將所有各部門通過光纜連接