2013海大講座電子第3圖論模型

3講 示法和稀疏矩陣表示法。在下面數(shù)據(jù)結(jié)構(gòu)的討論中，我們首先假設(shè)G(VE)是一個(gè)簡單無向圖，頂點(diǎn)集合V{v1,vn}E{e1,em}，記|V|n|E|m時(shí)

vi與vj當(dāng)G

零元素的行標(biāo)、列標(biāo)、非零元素的值即可，可以按如下方式在中無向圖和有向圖鄰接矩陣的使用上有很大差異。 令sparse命令，就可以把鄰接對于無向圖，由于鄰接矩陣是對稱陣，中只需使用鄰接矩陣的下三角元素，即只鄰接矩陣下三角元素中的非零元素。稀疏矩陣只是一種格式。 中，普通矩陣使用sparse命令變成稀疏矩陣，稀疏矩陣使用full命令變成普通矩陣。GVE,WP和Q,P用于存放G的最小生成樹中的頂點(diǎn)，集合Q存放G的最小生成樹中的邊。令集合P的初值為這時(shí)集合Q中包含了最小生成樹的所有邊。（1）P{v1}，Q（2）whileP~pvpPvVPPPQQM（充分大的實(shí)數(shù)）表示。引入01整數(shù)變量

(ij)表示從i到j(luò) zciji1s.

j2,,n,iu1

1uin ujukxkj(n2)(1xkj)(n3)xjk

k1,,n,j2,,n,j例 表 123456123456解構(gòu)造賦權(quán)圖GVE,W，其中頂點(diǎn)集Vv1v6，這里vi表示第iW

0

0

0

0

030(64.130(64.1)606（56561342圖 計(jì)算的程序如clc,clear');%a=a';a=sparse(a); cost=60*(6+L)%計(jì)算費(fèi)用vname=cellstr(int2str([1:6]'));%構(gòu)造頂點(diǎn)的字符set(h.Nodes,'shape','circle');%頂點(diǎn)畫成圓形h.EdgeType='segmented';%邊的連接為線段dolayout(h)%刷新圖形Dijkstra標(biāo)號算法和FloydG(VE,A0，其中頂點(diǎn)集V{v1vn}，鄰接矩陣 a1n aA

2n

an

ann

，當(dāng)v與v之間無邊時(shí) （ij aii0，i1,2,,nAk(i,j)min(Ak1(i,j),Ak1(i,k)Ak1(k,j))kijk1,2,n例2設(shè)備更新問題。某企業(yè)使用一臺設(shè)備，在每年年初，企業(yè)部門就要決定是購則需支付的。現(xiàn)在的問題是如何制定一個(gè)幾年之內(nèi)的設(shè)備更新計(jì)劃使得總的12345457解GVE,W，其中頂點(diǎn)集V{v1v2,v6}，這里vi（i1,,5(W

150

160

0 用最小的設(shè)備更新計(jì)劃，就是在圖G中求從v1到v6的費(fèi)用最短路。，（1）l(v10，對vv1l(vS0{v1}i0vSi（SiVSimin{l(v),l(u)代替l(vw(uvu和v之間邊的權(quán)值。計(jì)算min{l(v)}ui1Si1Si{ui1}v1vv()vSi之前的標(biāo)號()叫TvSi()叫標(biāo)號。算法就是不斷修改各頂點(diǎn)的T標(biāo)號，直至獲得標(biāo)號。若在算法運(yùn)行過程中，將每一頂點(diǎn)獲得標(biāo)號所由來的邊在圖上標(biāo)明，則v1v1v3v6464653圖2設(shè)備更新最小費(fèi)用示意圖clc,cleara(1,[2:6])=[15202737a(2,[3:6])=[152027a(3,[4:6])=[1621a(4,[5,6])=[1520];set(h.Nodes,'shape','circle');%頂點(diǎn)畫成圓形h.LayoutType='equilibrium';%圖形的布局是平衡的set(h.Nodes(path),'Color',[10.40.4])edges=getedgesbynodeid(h,get(h.Nodes(path),'ID'));set(edges,'LineColor',[100])dolayout(h)%刷新圖形例3求圖3所示網(wǎng)絡(luò)中從v1到v6 6 6 DVA,C表示圖3所示的有向圖，其中頂點(diǎn)集合V{v1,v2,v6}，弧的集合為A，容量矩陣C(cij)66的值為05690 C

000207000

8 00000 00000可以使用Ford-Fulkserson標(biāo)號算法求從v1v6的最大流，算法有標(biāo)號和調(diào)整兩個(gè)過程，這兩個(gè)過程的步驟如下,我們的算法從零流開始，即所有弧vivj上的流fij0。，表示在可能的增廣可以調(diào)整的流量。若(vxvyAfxycxy時(shí)，令ymin{cxyfxy,x}，則給頂點(diǎn)vy(vyvxAfyx0，令yminfyx,x}vy標(biāo)號為(vx,y，這里第一個(gè)標(biāo)號值vx，表示在可能的增廣，(vyvxfyx0vy標(biāo)v1到v6的增廣路，算法結(jié)束，此時(shí)所獲得的流就是①令vyv6②若vy的標(biāo)號為(vx,xfxyfxy6；若vy的標(biāo)號為(vx,xfyxfyx6最大流算法的實(shí)現(xiàn)可以使 圖4求得的最大流示意圖clc,cleara(2,[56])=[1a(3,[245])=[27a(4,[56])=[108];455最大流問題的網(wǎng)絡(luò)圖解圖論工具箱求解最大流令，只能解決權(quán)重都為正值，且兩個(gè)頂點(diǎn)之間容量都是2。求解的程序如下clc,clear,a=zeros(9);a(4,7)=5;a(4,9)=2;a(6,5)=8;56所示，邊上的權(quán)重表示容量，求該網(wǎng)絡(luò)所有的頂點(diǎn)對之間的最大11 5832543566GVE,C，其中頂點(diǎn)集合V1,2,3,4,5}E為邊的集

f fikfkj,k0

,i,j@text()=@table(tf輸出到屏幕);!c(2,3)=4;cc(3,5)=5;c@for(node(i)|i#ne#s#and#i#ne#t:@sum(node(j):f(i,j))=@sum(node(k)f(k,i))); 計(jì)劃評審方法（programevaluationandreviewtechnique,PERT）和關(guān)鍵路（criticalpathmethod,CPM）是網(wǎng)絡(luò)分析的重要組成部分，它廣泛地用于系統(tǒng)分析和項(xiàng)目管理。計(jì)劃評審與關(guān)鍵路線方法是在20世紀(jì)50年代提出并發(fā)展起來的，1956年，杜邦公司為了協(xié)調(diào)企業(yè)不同業(yè)務(wù)部門的系統(tǒng)規(guī)劃，提出了關(guān)鍵路。1958年，部在研制PERTCPM既有著相同的目標(biāo)應(yīng)用，又有很多相同的術(shù)語，這兩種方法已合并為法，在國外稱為PERT/CPM，在國內(nèi)稱為統(tǒng)籌方法（schedulingmethod定義1 件，A,B表示作業(yè)。由這種方法畫出的網(wǎng)絡(luò)圖稱為計(jì)劃網(wǎng)絡(luò)圖。7計(jì)劃網(wǎng)絡(luò)圖的基本畫法例 某項(xiàng)目工程由11項(xiàng)作業(yè)組（分別用代號A,B,,J,K表示其計(jì)劃完成時(shí)2作業(yè)流程數(shù)據(jù)計(jì)劃完成時(shí)間（天計(jì)劃完成時(shí)間（天A5—GB—HC—ID4BJF,G,E4AKF,FC,8圖8計(jì)劃網(wǎng)絡(luò) 弧的集合，鄰接矩陣Wwij)88 (ij)w

A,ij (ij) 18的最長路徑，網(wǎng)絡(luò)模型中有很多求最短路徑的算法，為~向圖G{VA,W~矩陣Wwij)88 (ij)

ij(ij)計(jì)算的程序如下a(4,6)=-15;a(5,6)=-21;a(5,7)=-25;a(5,8)=-35;a(6,7)=0;a(6,8)=-20;a(7,8)=-15; function[dist,mypath]=myfloyd(a,sb,db);%%輸出：dist—最短路的距離；mypath—最短路的路徑n=size(a,1);path=zeros(n);forforforif

parent=path(sb,:);%從起點(diǎn)sb到終點(diǎn)db的最短各頂點(diǎn)的前驅(qū)頂點(diǎn)parent(parent==0)=sbpath0，表示該頂點(diǎn)的前驅(qū)是起點(diǎn)mypath=db;t=db;p=parent(t);mypath=[p,mypath];PageRank算法是基于網(wǎng)頁分析對關(guān)鍵字匹配搜索結(jié)果進(jìn)行處理的。它借鑒傳統(tǒng)引個(gè)邊，鄰接矩陣B(bij)NN，如果從網(wǎng)頁i到網(wǎng)頁j有超，則bij1，否則為0。 cjbij，ribij 程，其狀態(tài)轉(zhuǎn)移規(guī)律用Markov鏈描述。定義矩陣A(aij)NN如下a1ddbij，i,j1,2,,N idd0.85A是Markov鏈的轉(zhuǎn)移概率矩陣，aij表示從頁面i轉(zhuǎn)移到頁面j的概率。根據(jù)Markov鏈的基本性質(zhì)，對于正則Markov鏈存在平穩(wěn)分布x[x1,,xN]T，滿足iNATxx xi1Nx表示在極限狀態(tài)（轉(zhuǎn)移次數(shù)趨于無限）下各網(wǎng)頁被的概率分布，將它定義為各網(wǎng)頁的PageRank值。假設(shè)x已經(jīng)得到，則它按分量滿足方程N(yùn)xkaik

(1d)d

xii

1xkk的PageRank值，即網(wǎng)絡(luò)上所有頁面“投票”給網(wǎng)頁k的最終值。7N69所示，求它的PageRank219網(wǎng)絡(luò)結(jié)構(gòu)示意圖B和MarkovA

000 000 B A

0

0.0250.0250.8750.025計(jì)算得到該Markovx0.2675 0.1323