1、第七章 圖與網(wǎng)絡(luò)分析模型選講,一、圖論的基本知識,1.圖的概念 定義 圖G(V,E)是指一個二元組(V(G),E(G)，其中: (1)V(G)=v1,v2, vn是非空有限集，稱為頂點(diǎn)集， (2)E(G)是V(G)中的元素對(vi,vj)組成的集合稱為邊集。,圖G：,V(G)=v1,v2,v3,v4 E(G)= e1,e2,e3,e4,e5,e6 e3=(v1,v3),若圖G是的邊是有方向的，稱G是有向圖，有向圖的邊稱為有向邊或弧。,常用術(shù)語 邊和它的兩端點(diǎn)稱為互相關(guān)聯(lián). 與同一條邊關(guān)聯(lián)的兩個端點(diǎn)稱 為相鄰的頂點(diǎn)，與同一個頂點(diǎn) 點(diǎn)關(guān)聯(lián)的兩條邊稱為相鄰的邊. 3)端點(diǎn)重合為一點(diǎn)的邊稱為環(huán).,4)

2、 若一對頂點(diǎn)之間有兩條以上的邊聯(lián)結(jié)，則這些邊稱為重邊 5)既沒有環(huán)也沒有重邊的圖，稱為簡單圖,6) 若圖G的每一條邊e 都賦以一個實(shí)數(shù)w(e)， 稱w(e)為邊e的權(quán)，G連同邊上的權(quán)稱為賦權(quán)圖 , 記為：G(V,E,W)， W=w(e)| eE,7) 圖G的中頂點(diǎn)的個數(shù)， 稱為圖G的階；圖中與某個頂點(diǎn)相關(guān)聯(lián)的邊的數(shù)目，稱為該頂點(diǎn)的度。 8）完全圖：若無向圖的任意兩個頂點(diǎn)之間都存在著一條邊，稱此圖為完全圖。,2.圖的矩陣表示 鄰接矩陣: (以下均假設(shè)圖為簡單圖). 圖G的鄰接矩陣是表示頂點(diǎn)之間相鄰關(guān)系的矩陣： A=(aij)，,若vi與vj相鄰,若vi與vj不相鄰,或權(quán)值，,或，,其中：,v1,

3、v2,v3,v4,v1,v2,v3,v4,5,4,3,1,無向圖G,鄰接矩陣A=(aij),有向圖G,鄰接矩陣A=(aij),v1,v2,v3,v4,v1,v2,v3,v4,5,4,3,1,二、最大流問題,定義：設(shè)G(V,E)為有向圖，若在每條邊e上定義一個非負(fù)權(quán)c，則稱圖G為一個網(wǎng)絡(luò)，稱c為邊e的容量函數(shù)， 記為c(e)。 若在有向圖G(V,E)中有兩個不同的頂點(diǎn)vs與vt ， 若頂點(diǎn)vs只有出度沒有入度，稱vs為圖G的源， 若頂點(diǎn)vt只有入度沒有出度，稱為G的匯， 若頂點(diǎn)v 既不是源也不是匯，稱為v中間頂點(diǎn)。,v2,v4,v1,v3,vs,vt,4,8,3,7,5,7,3,7,設(shè)u,v網(wǎng)絡(luò)

4、G(V,E)的相鄰頂點(diǎn)，邊(u,v)上的函數(shù)f(u,v)稱為邊(u,v)上的實(shí)際流量； 若對網(wǎng)絡(luò)G(V,E)的任意相鄰頂點(diǎn)u,v 均成立： 0 f(u,v) c(u,v) ， 稱該網(wǎng)絡(luò)為相容網(wǎng)絡(luò)。,若v為網(wǎng)絡(luò)G(V,E)的中間頂點(diǎn)，,有：,網(wǎng)絡(luò)的總流量為從源vs 流出的總流量：,流入?yún)Rvt 總流量：,定義：設(shè)網(wǎng)絡(luò)G(V,E)為相容網(wǎng)絡(luò)，u,v是G的相鄰頂點(diǎn)， G的容量函數(shù)為c(u,v)，實(shí)際流量函數(shù)為f(u,v)，vs 和vt分別為G(V,E)的源和匯，V(f)為從源vs流出的總流量，,若：,則稱該網(wǎng)絡(luò)稱為守恒網(wǎng)絡(luò)。 守恒網(wǎng)絡(luò)中的流 f 稱為可行流。,若存在一個可行流f *，使得對所有可行流

5、f 都有V(f *) V(f )成立，則稱f *為最大流。,最大流模型：,s.t:,例7.1分組交換技術(shù)在計(jì)算機(jī)網(wǎng)絡(luò)中發(fā)揮著重要作用，信息從源節(jié)點(diǎn)到目的節(jié)點(diǎn)不再需要一條固定的路徑，而是將其分割為幾組，通過不同的路徑傳輸?shù)侥康墓?jié)點(diǎn)，目的節(jié)點(diǎn)再重新組合還原文件?，F(xiàn)考察如圖所示的網(wǎng)絡(luò)，圖中兩節(jié)點(diǎn)間的數(shù)字表示兩交換機(jī)間可用的帶寬，此時從節(jié)點(diǎn)1到節(jié)點(diǎn)9的最大帶寬為多少？,設(shè)fij為從vi到vj的實(shí)際流量，得一個9階方陣：F=( fij),記容量矩陣為C =,0 2.5 0 5.6 6.1 0 0 0 0 0 0 7.1 0 0 3.6 0 0 0 0 0 0 0 0 0 0 3.4 0 0 0 0 0

6、4.9 0 7.4 0 0 0 2.4 0 0 0 7.2 5.7 0 0 0 0 3.8 0 0 0 0 5.3 4.5 0 0 0 0 0 3.8 0 0 6.7 0 0 0 0 0 0 0 0 7.4 0 0 0 0 0 0 0 0 0,sets: node/1.9/; arc(node,node):c,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

7、; for(arc:bnd(0,f,c);,data: c= 0 2.5 0 5.6 6.1 0 0 0 0 0 0 7.1 0 0 3.6 0 0 0 0 0 0 0 0 0 0 3.4 0 0 0 0 0 4.9 0 7.4 0 0 0 2.4 0 0 0 7.2 5.7 0 0 0 0 3.8 0 0 0 0 5.3 4.5 0 0 0 0 0 3.8 0 0 6.7 0 0 0 0 0 0 0 0 7.4 0 0 0 0 0 0 0 0 0; enddata,該程序運(yùn)行結(jié)果： 最大流：14.2 F(1,2)=2.5, F(1,4)=5.6,F(1,5)=6.1,F(2,3)=3.4,F

8、(2,6)=1.5, F(3,8)=3.4,F(4,5)=3.3,F(4,7)=2.3,F(5,2)=2.4,F(5,6)=7, F(6,8)=4,F(6,9)=4.5,F(7,9)=2.3,F(8,9)=7.4,0 2.5 0 5.6 6.1 0 0 0 0 0 0 7.1 0 0 3.6 0 0 0 0 0 0 0 0 0 0 3.4 0 0 0 0 0 4.9 0 7.4 0 0 0 2.4 0 0 0 7.2 5.7 0 0 0 0 3.8 0 0 0 0 5.3 4.5 0 0 0 0 0 3.8 0 0 6.7 0 0 0 0 0 0 0 0 7.4 0 0 0 0 0 0 0 0

9、 0 x=1,1,1,2,2,3,4,4,5,5,5,6,6,6,7,7,8,9; y=2,4,5,3,6,8,5,7,2,6,7,3,8,9,6,9,9,9; z=2.5,5.6,6.1,7.1,3.6,3.4,4.9,7.4,2.4,7.2,5.7,3.8,5.3,4.5,3.8,6.7,7.4,0;,Matlab中求最大流的命令： graphmaxflow(f,a,b),clc,clear x=1,1,1,2,2,3,4,4,5,5,5,6,6,6,7,7,8,9; y=2,4,5,3,6,8,5,7,2,6,7,3,8,9,6,9,9,9; z=2.5,5.6,6.1,7.1,3.6,

10、3.4,4.9,7.4,2.4,7.2,5.7,3.8,5.3,4.5,3.8,6.7,7.4,0; f=sparse(x,y,z) flow,flowmat=graphmaxflow(f,1,9) name1(1:9,1)=v; name2=int2str(1:9); name=cellstr(strcat(name1,name2); view(biograph(flowmat,name,ShowWeights,on),三、旅行售貨員問題（TSP問題）,一個旅行商，從城市1出發(fā)，要遍訪城市1,2,3,n各一次，最后返回城市1。若從城市i到j(luò)的旅費(fèi)為cij， 問他應(yīng)按怎樣的次序訪問這些城市，能

11、使得總旅費(fèi)最少？ 用圖論語言描述：在賦權(quán)圖中，尋找一條經(jīng)過所有節(jié)點(diǎn)，并回到原點(diǎn)的最短路。 包含圖G的每個頂點(diǎn)的路稱為哈密頓路；閉的哈密頓路稱為哈密頓圈。 到目前為止，TSP問題還沒有有效解決方法，現(xiàn)有的方法都是尋找近似最優(yōu)的哈密頓圈，常用方法有邊替換法、遺傳算法、模擬退火法、蟻群算法等。,引入0-1變量：xij=,1，由第i城市進(jìn)入第j城市，且i j,0，其它,目標(biāo)函數(shù)：,對規(guī)模不大的TSP問題可將其轉(zhuǎn)化為數(shù)學(xué)規(guī)劃問題：,j=1,2,3,n,i=1,2,3,n,到此得到了一個模型，它是一個指派問題的整數(shù)規(guī)劃模型。但以上兩個條件對于TSP來說并不充分， 僅僅是必要條件。 例如：,以上兩個條件都滿

12、足，但它顯然不是TSP的解， 它存在兩個子巡回。,則可以避免產(chǎn)生子巡回。,若在原模型上添加變量ui ， 并附加下面形式的約束條件：,目標(biāo)函數(shù)：,s.t：,i=2,3,n,i,j=1,2,3,n,j=1,2,3,n,i=1,2,3,n,TSP問題的數(shù)學(xué)規(guī)劃模型：,例7.2 (TSP問題) 已知9個城市間的旅行費(fèi)用（見表）問他應(yīng)按怎樣的次序訪問這些城市，能使得總旅費(fèi)最少？,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,

13、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, 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 9,

14、1 2 3 4 5 6 7 8 9,s.t：,i,j=1,2,3,n,sets: city /1.9/: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)=0); for(link:bin(x);,data: c=0, 3.1, 5

15、.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.8, 7.5, 8.8, 6.4, 5.3, 10.8,11.3, 6.1, 0, 6.6, 4.9, 7.3,

16、 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; enddata,Objective value: 49.10000 X( 1, 4) 1.000000 X( 2, 1) 1.000000 X( 3, 2) 1.000000 X( 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

17、,2,1 訪問這些城市時總費(fèi)用最小，最小費(fèi)用：49.1,ei與vi-1和vi關(guān)聯(lián)，稱 為圖G的,四、最短路問題,道路與軌道：在圖G(V,E)中，設(shè),一條道路，k為路長，v0為道路P的起點(diǎn)vt為終點(diǎn)， 各邊相異的道路稱為行跡， 頂點(diǎn)不同且邊也不同的道路稱為軌道（路徑）。 最短路問題：對賦權(quán)圖G(V,E,W)，在連接指定起點(diǎn)v0與終點(diǎn)vt的所有軌道P中，尋找一條權(quán)數(shù)之和最小的軌道。,數(shù)學(xué)模型： 設(shè)圖G(V,E,W), 頂點(diǎn)v0,vtV, 邊 e E ，w(e)為邊e的權(quán)數(shù)，P(v0,vt)是起點(diǎn)為v0終點(diǎn)為vt為任意一條軌道， 所有這些軌道的全體記為：S(P) W(P)為軌道P(v0,vt)上各邊

18、的權(quán)數(shù)之和，,最短路問題需要求出： （1）權(quán)數(shù)之和最小的軌道（2）該軌道的權(quán)數(shù)之和 求解此問題的方法有：Dijkstra算法、floyd算法，遺傳算法、模擬退火、蟻群算法等。,Dijkstra算法：（算法具體內(nèi)容略） 是用來求指定兩點(diǎn)A與B之間的最短路的， 在matlab中使用命令graphshortestpath實(shí)現(xiàn)。 調(diào)用格式：dist,path=graphshortestpath(DG,A,B) dist： A與B之間的最短路的長度 path： A與B之間的最短路的路徑 DG：權(quán)數(shù)鄰接矩陣 由權(quán)數(shù)鄰接矩陣畫圖的命令： view(biograph(DG,ShowWeights,on),例7.3 某地10個點(diǎn)v1,v2,v10間的道路連接情況為：,相鄰點(diǎn) 距離 相鄰點(diǎn) 距離 相鄰點(diǎn) 距離 相鄰點(diǎn) 距離 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.6 45