課件-圖論和網(wǎng)絡(luò)分析算法及Matlab實(shí)現(xiàn)

圖論基本模型算法及matlab實(shí)現(xiàn)

一、圖論的基本概念

二、圖論模型與算法三、Matlab實(shí)現(xiàn)1.圖論簡介起源：1736年Eular解決“哥尼斯堡”七橋問題1.圖論簡介

圖G(V,E)

?頂點(diǎn)集合V

?邊集合

E

?一條邊e

有兩個(gè)頂點(diǎn){u，v}，記為e=uv圖G1.圖論簡介

圖G(V,E)

?頂點(diǎn)集合V

?邊集合

E

?一條邊e

有兩個(gè)頂點(diǎn){u,v}，記為e=uv無向圖G無序頂點(diǎn)對(duì)1.圖論簡介

圖G(V,E)

?頂點(diǎn)集合V

?邊集合

E

?一條邊e

有兩個(gè)頂點(diǎn){u，v}，記為e=uv圖G1.圖論簡介

圖G(V,E)

?頂點(diǎn)集合V

?邊集合

E

?一條邊e

有兩個(gè)頂點(diǎn){u，v}，記為e=uv簡單圖G無環(huán)邊和重邊1.圖論簡介

圖G(V,E)

?頂點(diǎn)集合V

?邊集合

E

?一條邊e

有兩個(gè)頂點(diǎn){u，v}，記為e=uv?u是v的鄰居節(jié)點(diǎn)?v的度d(v)：與v關(guān)聯(lián)的邊數(shù)1.圖論簡介

圖G(V,E)

?頂點(diǎn)集合V

?邊集合

E

?一條邊e

有兩個(gè)頂點(diǎn){u，v}，記為e=uv?u是v的鄰居節(jié)點(diǎn)?v的度d(v)：與v關(guān)聯(lián)的邊數(shù)?v的鄰域N(v)：所有v的鄰居的集合1.圖論簡介

完全圖：任意兩點(diǎn)有邊相連，用表示

路與圈圖中一個(gè)點(diǎn)邊接續(xù)交替且不重復(fù)出現(xiàn)的序列稱為路；若僅有起點(diǎn)和終點(diǎn)重復(fù)，則稱為圈。3.路與圈圖中一個(gè)點(diǎn)邊接續(xù)交替且不重復(fù)出現(xiàn)的序列稱為路；若僅有起點(diǎn)和終點(diǎn)重復(fù)，則稱為圈。路與圈圖中一個(gè)點(diǎn)邊接續(xù)交替且不重復(fù)出現(xiàn)的序列稱為路；若僅有起點(diǎn)和終點(diǎn)重復(fù)，則稱為圈。匹配：一個(gè)邊集合M,任意兩條邊不相鄰；覆蓋所有頂點(diǎn)的匹配叫完美匹配。關(guān)聯(lián)矩陣與鄰接矩陣

關(guān)聯(lián)矩陣與鄰接矩陣

有向圖與無向圖，圈，回路比較：路有向路二.最短路問題

v5v1v3v6v4v2v7255233575711算法：Dijkstra算法（Dijkstra，1959）Dijkstra,E.W.(1959).Anoteontwoproblemsinconnexionwithgraphs.NumerischeMathematik1,269–271.算法思想：Bellman最優(yōu)化原理若P是網(wǎng)絡(luò)G中從Vs到Vt的一條最短路，Vl是P中除Vs與Vt外的任何一個(gè)中間點(diǎn)，則沿P從Vs到Vl的一條路P1亦必是Vs到Vl的最短路。Dijkstra算法-標(biāo)號(hào)法由圖G建立一步可達(dá)距離陣D=(dij)n×n給V1(Vs)括號(hào)(l1,Vk)=(0,s)給出已標(biāo)號(hào)集合I和未標(biāo)號(hào)集合J的元素對(duì)于給定的I和J，確定集合A={aij|Vi∈I，Vj∈J}

計(jì)算距離給Vk括號(hào)(lk,Vh)lk=lh+WhkI=I+{Vk}J=J–{Vk}A=φ或J＝φ從Vt

逆向搜索雙括號(hào)，可得最小路P途徑各點(diǎn)及最小路距離ENDNYDijkstra算法用標(biāo)號(hào)法解例v5v1v3v6v4v2v7255233575711[0，v1][2，v1][3，v1][4，v2][7，v3][8，v5][13，v6]最短距為13；最短路為v1-v2-v3-v5-v6-v7。最短路問題應(yīng)用廠址選擇廠址布局設(shè)備更新網(wǎng)絡(luò)線路安裝工程設(shè)計(jì)企業(yè)管理最短路問題的應(yīng)用例子

某汽車公司正在制訂5年內(nèi)購買汽車的計(jì)劃。下面給出一輛新汽車的價(jià)格以及一輛汽車的使用維修費(fèi)用(萬元)：

年份 1 2 3 4 5年初價(jià)格 11 11 12 12 13

使用年數(shù)0～11～22～3 3～44～5年維護(hù)費(fèi)用5 6 8 11 18

試用圖論中求最短路的方法確定公司可采用的最優(yōu)策略。解：設(shè)Vi—i年初購進(jìn)一臺(tái)新設(shè)備aij—i年初購進(jìn)之新設(shè)備使用到第j年初ωij—i年初購進(jìn)之新設(shè)備使用到第j年初之總費(fèi)用

方法：以年號(hào)作頂點(diǎn)繪圖，連線表示連續(xù)使用期間，以費(fèi)用作路長。費(fèi)用矩陣方法：以年號(hào)作頂點(diǎn)繪圖，連線表示連續(xù)使用期間，以

費(fèi)用作路長?？芍疃藤M(fèi)用流（相當(dāng)于最短路）

P：V1V3V6

或者是V1V4V6

|

P|=53萬元

結(jié)論：公司五年期設(shè)備更新方案有兩個(gè)：A與B，總費(fèi)用均為53萬元。

A方案：第1年初購置設(shè)備使用到第3年初,第3年初再購置新設(shè)備使用到第5年末（第6年初）

B方案：第1年初購置設(shè)備使用到第4年初，第4年初再購置新設(shè)備使用到第5年末（第6年初）

Matlab程序?qū)崿F(xiàn)

Matlab程序?qū)崿F(xiàn)1寫出鄰接矩陣輸入臨接矩陣：W=[0218infinfinfinf

20inf61infinfinf

1inf07infinf9inf

8670512inf

inf1inf503

inf9

infinfinf130

46

infinf92inf4

03infinfinf

inf96

30];function[d,path]=dijkstra(W,s,t)%s起點(diǎn)，t終點(diǎn)[n,m]=size(W);ix=(W==0);W(ix)=inf;ifn~=m,error('SquareWrequired');endvisited(1:n)=0;dist(1:n)=inf;parent(1:n)=0;dist(s)=0;d=inf;fori=1:(n-1),ix=(visited==0);vec(1:n)=inf;vec(ix)=dist(ix);[a,u]=min(vec);visited(u)=1;

forv=1:n,

if(W(u,v)+dist(u)<dist(v)),dist(v)=dist(u)+W(u,v);parent(v)=u;

end;

end;endifparent(t)~=0,path=t;d=dist(t);

whilet~=s,p=parent(t);path=[ppath];t=p;

end;end;樹v1v2v3v5v4

特點(diǎn)：連通、無圈?！獰o圈的連通圖，記為T。v1v2v3v5v4樹的性質(zhì)：（1）樹的任2點(diǎn)間有且僅有1條路；（2）在樹中任去掉1邊，則不連通；（3）在樹中不相鄰2點(diǎn)間添1邊，恰成1圈；（4）若樹T有n個(gè)頂點(diǎn)，則T有n-1條邊。圖的支撐樹

若圖G=（V，E）的子圖T=（V，E’）是樹，則稱T為G的支撐樹。特點(diǎn)——邊少、點(diǎn)不少。性質(zhì)：G連通，則G必有支撐樹。證：破圈、保連通。最小支撐樹問題

例2求如圖網(wǎng)絡(luò)的最小支撐樹。v5v1v3v6v4v2v7255233575711Kruskal,J.B.(1956).OntheShortestSpanningSubtreeofaGraphandtheTravelingSalesmanProblem.ProceedingsoftheAmericanMathematicalSociety7,48-50.

避圈法是一種選邊的過程，其步驟如下：1.從圖D中任選一點(diǎn)vi，找出與vi相關(guān)聯(lián)的權(quán)最小的邊[vi，vj]，得第二個(gè)頂點(diǎn)vj；2.把頂點(diǎn)集V分為互補(bǔ)的兩部分V1,1，其中對(duì)G中各邊按權(quán)大小順序排列，不妨設(shè)為W1≤W2≤…≤Wm填寫Wj對(duì)應(yīng)的各邊aj

S=φ，i=0，j=1{aj}∪S構(gòu)成回路？|S|=n-1ei+1=ajS={ei+1}∪Si=i+1j=j+1j=j+1T*=S打印T*ENDYYNN用避圈法解例題v5v1v3v6v4v2v7255233575711?最小部分樹如圖上紅線所示；最小權(quán)和為14。思考：破圈法是怎樣做的呢？——見圈就破，去掉其中權(quán)最大的。最小支撐樹問題的應(yīng)用例子已知有A、B、C、D、E、F六個(gè)城鎮(zhèn)間的道路網(wǎng)絡(luò)如圖，現(xiàn)要在六個(gè)城鎮(zhèn)間架設(shè)通訊網(wǎng)絡(luò)（均沿道路架設(shè)），每段道路上的架設(shè)費(fèi)用如圖。求能保證各城鎮(zhèn)均能通話且總架設(shè)費(fèi)用最少的架設(shè)方案。6EACBFD5109353978284三.最大流問題

v4v2vsv1vtv3213145325三.最大流問題1.問題已知網(wǎng)絡(luò)D=（V，A，C），其中V為頂點(diǎn)集，A為弧集，C={cij}為容量集，cij為?。╲i，vj）上的容量?，F(xiàn)D上要通過一個(gè)流f={fij}，其中fij為?。╲i，vj）上的流量。問應(yīng)如何安排流量fij可使D上通過的總流量v最大？v4v2vsv1vtv3213145325可采用線性規(guī)劃的單純型法求解（容量約束）（平衡條件）問題：最大流問題的決策變量、目標(biāo)函數(shù)、約束條件各是什么？2.數(shù)學(xué)模型3.基本概念與定理如：在前面例舉的網(wǎng)絡(luò)流問題中，若已給定一個(gè)可行流（如括號(hào)中后一個(gè)數(shù)字所示），請(qǐng)指出相應(yīng)的弧的類型。v4v2vsv1vtv3（2，2）（1，1）（3，3）（1，1）（4，3）（5，1）（3，0）（2，1）（5，3）（2）可增值路（增廣路）v4v2vsv1vtv3（2，2）（1，1）（3，3）（1，1）（4，3）（5，1）（3，0）（2，1）（5，3）路路（2）可增值路（增廣路）路路v4v2vsv1vtv3（2，2）（1，1）（3，3）（1，1）（4，3）（5，1）（3，0）（2，1）（5，3）算法設(shè)計(jì)思想

最大流的判別條件

任意一個(gè)可行流(例如零值流)開始，若能找到一條s-t增廣路P，則沿P修改流的值，得到一個(gè)更大的流f；若不存在s-t增廣路，則由定理5.2，f就是最大流，算法終止。關(guān)鍵：在給定可行流

f時(shí)，如何找s-t增廣路或判斷s-t增廣路不存在?

Ford-Fulkerson標(biāo)號(hào)法

例5用標(biāo)號(hào)法求下面網(wǎng)絡(luò)的最大流。v4v2vsv1vtv3（2，2）（1，1）（3，3）（1，1）（4，3）（5，1）（3，0）（2，1）（5，3）2020當(dāng)前流即為最大流，流值為5

割集與割容量

例4對(duì)于下圖，若V1={vs，v1}，請(qǐng)指出相應(yīng)的割集與割容量。解：（4）流量與割容量的關(guān)系最大流最小割定理：v4v2vsv1vtv3（2，2）（1，0）（3，3）（1，0）（4，3）（5，2）（3，0）（2，2）（5，3）最大流問題的應(yīng)用例子汽車由A城通往B城的可能的路線如下圖所示。環(huán)境保護(hù)部門擬建立足夠數(shù)量的汽車尾氣檢查站，以便使每輛汽車至少必須經(jīng)過一個(gè)檢查站。建立檢查站的費(fèi)用根據(jù)各路段的條件而有所不同(如圖上數(shù)字所示)。若求這個(gè)問題的最小費(fèi)用解，可使用

模型。

a.最短路模型；b.最大流模型；c.最小支撐樹模型AacbdefgB824452643367378最小費(fèi)用流問題

延伸問題最小費(fèi)用流中國郵遞員問題、歐拉回路（邊）旅行商問題、漢密爾頓圈（點(diǎn)）可平面化問題指派問題統(tǒng)籌網(wǎng)絡(luò)計(jì)劃匹配問題無圈網(wǎng)絡(luò)：拓?fù)渑判?動(dòng)態(tài)規(guī)劃圈的檢測正費(fèi)用網(wǎng)絡(luò)：Dijkstra算法（1959）一般網(wǎng)絡(luò)，單一起點(diǎn)（或終點(diǎn)）Bellman-Ford算法(1956)：

O(mn)一般網(wǎng)絡(luò)，所有點(diǎn)對(duì)Floyd-Warshall算法(1962)：

O(n3)負(fù)圈檢測最短路算法：標(biāo)號(hào)設(shè)定/修正算法破圈法-----復(fù)雜度高避圈法----貪婪算法(GreedyAlgorithm)Kruskal算法（1956）Prim算法（1957）：即“邊割法”Dijkstra算法（1959）Sollin算法（1961）最?。ㄉ桑渌惴ㄔ鰪V路算法Ford-Fulkerson標(biāo)號(hào)算法(1956)最大容量增廣路算法容量變尺度算法最短增廣路算法：O(n2m)預(yù)流推進(jìn)算法最高標(biāo)號(hào)預(yù)流推進(jìn)算法：O(n2m1/2)最大流算法實(shí)際計(jì)算效率高消圈算法最小費(fèi)用路算法原始-對(duì)偶算法Ford和Forkerson(1957,1962)瑕疵算法(Out-Of-KilterAlgorithm)松弛(Relaxation)算法網(wǎng)絡(luò)單純形算法最小費(fèi)用流算法實(shí)際計(jì)算效率高二部圖匹配增廣路算法：O(mn)簡單網(wǎng)絡(luò)上的最大流算法：O(mn1/2)一般圖匹配“花”算法:O(n3)二部賦權(quán)匹配（指派問題）最小費(fèi)用流算法（如匈牙利算法）:O(n3)一般賦權(quán)匹配原始-對(duì)偶算法:O(n3)匹配算法Matlab圖論工具箱命令名功能graphallshortestpaths求圖中所有頂點(diǎn)對(duì)之間的最短距離graphconncomp找無向圖的連通分支，或有向圖的強(qiáng)弱連通分支graphisdag測試有向圖是否含有圈，不含圈返回1，否則返回0graphisomorphism確定兩個(gè)圖是否同構(gòu)，同構(gòu)返回1，否則返回0graphisspantree確定一個(gè)圖是否是生成樹，是返回1，否則返回0graphmaxflow計(jì)算有向圖的最大流graphminspantree在圖中找最小生成樹graphpred2path把前驅(qū)頂點(diǎn)序列變成路徑的頂點(diǎn)序列g(shù)raphshortestpath求圖中指定的一對(duì)頂點(diǎn)間的最短距離和最短路徑graphtopootder執(zhí)行有向無圈圖的拓?fù)渑判騡raphtraverse求從一頂點(diǎn)出發(fā)，所能遍歷圖中的頂點(diǎn)[i,j,v]=find(G);S=sparse(i,j,v,n,n);圖論工具包中的命令要求輸入的鄰接矩陣為稀疏矩陣，我們用下面的命令來實(shí)現(xiàn)：

圖的最短路徑graphallshortestpaths函數(shù)的命令格式[dist]=graphallshortestpaths(G)[dist]=graphallshortestpaths(G,...’Directed’,DirectedValue,...)[dist]=graphallshortestpaths(G,...’Weights’,WeightsValue,...)

例：創(chuàng)建并顯示一個(gè)含有6個(gè)結(jié)點(diǎn)11條邊的有向圖w=[4199513215453832362921];%權(quán)值向量dg=sparse([61223445561],[26354163435],w);%構(gòu)造的稀疏矩陣表示圖h=view(biograph(dg,[],'ShowWeights','on'))%顯示圖的結(jié)構(gòu)dist=graphallshortestpaths(dg)%顯示圖中每對(duì)結(jié)點(diǎn)之間的最短路徑dist=

0

136

53

57

21

95

111

0

51

66

32

104

60

94

0

15

81

53

45

79

67

0

66

38

81

115

32

36

0

74

89

41

29

44

73

0求給定兩點(diǎn)間最短路徑---graphshortestpath函數(shù)：[dist,path,pred]=graphshortestpath(S,ss,se,’Directed’,1,’Method’,’Bellman-Ford’)S：圖的稀疏矩陣ss,se：

分別代表起點(diǎn)和終點(diǎn)‘Directed’：1表示有向圖，0或false表示無向圖‘Method’：使用算法，默認(rèn)值為Dijkstra算法輸出dist：距離；path：路徑

Matlab程序：clc,clearA(1,2)=2;A(1,3)=5;A(1,4)=3;A(2,3)=2;A(2,6)=7;A(3,4)=1;A(3,5)=3;A(3,6)=5;A(4,5)=5;A(5,6)=1;A(5,7)=7;A(6,7)=5;A=A’%matlab工具包要求數(shù)據(jù)為下三角矩陣[i,j,v]=find(A);S=sparse(i,j,v,7,7);[dist,path,pred]=graphshortestpath(S,1,7,’Directed’,0)數(shù)學(xué)建模競賽涉及題目1994修路路線設(shè)計(jì)問題

1998災(zāi)情巡查路線設(shè)計(jì)

2005DVD在線租賃問題

2007乘公交看奧運(yùn)問題

2011圍追堵截崗?fù)ぴO(shè)置問題1994全國大學(xué)生數(shù)學(xué)建模競賽

要在一山區(qū)修建公路,首先測得一些地點(diǎn)的高程,數(shù)據(jù)見表1(平面區(qū)域0≤x≤5600,0≤y≤4800,表中數(shù)據(jù)為坐標(biāo)點(diǎn)的高程,單位:米).數(shù)據(jù)顯示:

在y=3200處有一東西走向的山峰;從坐標(biāo)(2400,2400)到(4800,0)有一西北---東南走向的山谷;在(2000,2800)附近有一山口湖,其最高水位略高于1350米,雨季在山谷中形成一溪流.經(jīng)調(diào)查知,雨量最大時(shí)溪流水面寬度w與(溪流最深處)的x坐標(biāo)的關(guān)系可近似表示為w(x)=((x-24003/4)/2)+5(2400≤x≤4000).公路從山腳(0,800)處開始,經(jīng)居民點(diǎn)(4000,2000)至礦區(qū)(2000,4000).已知路段工程成本及對(duì)路段坡度α(上升高程與水平距離之比)的限制如表2.

題目要求試給出一種線路設(shè)計(jì)方案,包括原理、方法及比較精確的線路位置(含橋梁、隧道),并估算該方案的總成本.

如果居民點(diǎn)改為3600≤x≤4000,2000≤y≤2400的居民區(qū),公路只須經(jīng)過居民區(qū)即可,那么你的方案需要有什么改變？表1

表2

工程種類┃一般路段┃橋梁┃隧道_________┃_______工程成本(元/米)┃300┃2000┃1500(長度≤300米);3000(長度>300米)對(duì)坡度α的限制┃α<0.125┃α=0┃α<0.100模型計(jì)算方法(1)

對(duì)地圖網(wǎng)格加密，形成圖。(2)

計(jì)算網(wǎng)格的距離，用費(fèi)用作為權(quán)值。(3)求賦權(quán)圖兩點(diǎn)間的最短距離。

例：逃生路線問題n*n網(wǎng)格節(jié)點(diǎn)上有m個(gè)房間，逃到邊上節(jié)點(diǎn)就算逃生成功如何規(guī)劃逃生路線，使這些路線互不相交？網(wǎng)絡(luò)優(yōu)化問題的例子

可以變成最大流問題逃生成功沒有逃生路線m個(gè)房間是供應(yīng)節(jié)點(diǎn)（源，供應(yīng)量為１）只有邊上節(jié)點(diǎn)可以是吸收節(jié)點(diǎn)（匯，吸收量為１）多源多匯，容易變成單源單匯每條邊容量為１每個(gè)節(jié)點(diǎn)容量為１（通過增加節(jié)點(diǎn)和邊，變成邊容量）逃生路線問題變成最大流問題逃生成功沒有逃生路線例：空間實(shí)驗(yàn)問題某航天公司計(jì)劃進(jìn)行一次空間載人飛行，宇航員將在飛行中進(jìn)行一系列科學(xué)實(shí)驗(yàn)。目前該公司收到了多個(gè)不同的科學(xué)實(shí)驗(yàn)申請(qǐng)，完成每個(gè)實(shí)驗(yàn)要求攜帶相應(yīng)的一種或多種儀器設(shè)備（不同的實(shí)驗(yàn)所需要的儀器設(shè)備中有些可能是相同的，而另外有些可能是不同的）。已知完成每個(gè)實(shí)驗(yàn)后公司所得到的相應(yīng)報(bào)酬（不同實(shí)驗(yàn)的報(bào)酬可能不同），并已知飛行器攜帶每種儀器設(shè)備的相應(yīng)費(fèi)用（不同儀器設(shè)備的費(fèi)用可能不同）。公司希望你幫助選定此次飛行究竟從事哪