2013海大讲座电子第3图论模型

3讲 示法和稀疏矩阵表示法。在下面数据结构的讨论中，我们首先假设G(VE)是一个简单无向图，顶点集合V{v1,vn}E{e1,em}，记|V|n|E|m时

vi与vj当G

零元素的行标、列标、非零元素的值即可，可以按如下方式在中无向图和有向图邻接矩阵的使用上有很大差异。 令sparse命令，就可以把邻接对于无向图，由于邻接矩阵是对称阵，中只需使用邻接矩阵的下三角元素，即只邻接矩阵下三角元素中的非零元素。稀疏矩阵只是一种格式。 中，普通矩阵使用sparse命令变成稀疏矩阵，稀疏矩阵使用full命令变成普通矩阵。GVE,WP和Q,P用于存放G的最小生成树中的顶点，集合Q存放G的最小生成树中的边。令集合P的初值为这时集合Q中包含了最小生成树的所有边。（1）P{v1}，Q（2）whileP~pvpPvVPPPQQM（充分大的实数）表示。引入01整数变量

(ij)表示从i到j zciji1s.

j2,,n,iu1

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

k1,,n,j2,,n,j例 表 123456123456解构造赋权图GVE,W，其中顶点集Vv1v6，这里vi表示第iW

0

0

0

0

030(64.130(64.1)606（56561342图 计算的程序如clc,clear');%a=a';a=sparse(a); cost=60*(6+L)%计算费用vname=cellstr(int2str([1:6]'));%构造顶点的字符set(h.Nodes,'shape','circle');%顶点画成圆形h.EdgeType='segmented';%边的连接为线段dolayout(h)%刷新图形Dijkstra标号算法和FloydG(VE,A0，其中顶点集V{v1vn}，邻接矩阵 a1n aA

2n

an

ann

，当v与v之间无边时 （ij aii0，i1,2,,nAk(i,j)min(Ak1(i,j),Ak1(i,k)Ak1(k,j))kijk1,2,n例2设备更新问题。某企业使用一台设备，在每年年初，企业部门就要决定是购则需支付的。现在的问题是如何制定一个几年之内的设备更新计划使得总的12345457解GVE,W，其中顶点集V{v1v2,v6}，这里vi（i1,,5(W

150

160

0 用最小的设备更新计划，就是在图G中求从v1到v6的费用最短路。，（1）l(v10，对vv1l(vS0{v1}i0vSi（SiVSimin{l(v),l(u)代替l(vw(uvu和v之间边的权值。计算min{l(v)}ui1Si1Si{ui1}v1vv()vSi之前的标号()叫TvSi()叫标号。算法就是不断修改各顶点的T标号，直至获得标号。若在算法运行过程中，将每一顶点获得标号所由来的边在图上标明，则v1v1v3v6464653图2设备更新最小费用示意图clc,cleara(1,[2:6])=[15202737a(2,[3:6])=[152027a(3,[4:6])=[1621a(4,[5,6])=[1520];set(h.Nodes,'shape','circle');%顶点画成圆形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所示网络中从v1到v6 6 6 DVA,C表示图3所示的有向图，其中顶点集合V{v1,v2,v6}，弧的集合为A，容量矩阵C(cij)66的值为05690 C

000207000

8 00000 00000可以使用Ford-Fulkserson标号算法求从v1v6的最大流，算法有标号和调整两个过程，这两个过程的步骤如下,我们的算法从零流开始，即所有弧vivj上的流fij0。，表示在可能的增广可以调整的流量。若(vxvyAfxycxy时，令ymin{cxyfxy,x}，则给顶点vy(vyvxAfyx0，令yminfyx,x}vy标号为(vx,y，这里第一个标号值vx，表示在可能的增广，(vyvxfyx0vy标v1到v6的增广路，算法结束，此时所获得的流就是①令vyv6②若vy的标号为(vx,xfxyfxy6；若vy的标号为(vx,xfyxfyx6最大流算法的实现可以使 图4求得的最大流示意图clc,cleara(2,[56])=[1a(3,[245])=[27a(4,[56])=[108];455最大流问题的网络图解图论工具箱求解最大流令，只能解决权重都为正值，且两个顶点之间容量都是2。求解的程序如下clc,clear,a=zeros(9);a(4,7)=5;a(4,9)=2;a(6,5)=8;56所示，边上的权重表示容量，求该网络所有的顶点对之间的最大11 5832543566GVE,C，其中顶点集合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))); 计划评审方法（programevaluationandreviewtechnique,PERT）和关键路（criticalpathmethod,CPM）是网络分析的重要组成部分，它广泛地用于系统分析和项目管理。计划评审与关键路线方法是在20世纪50年代提出并发展起来的，1956年，杜邦公司为了协调企业不同业务部门的系统规划，提出了关键路。1958年，部在研制PERTCPM既有着相同的目标应用，又有很多相同的术语，这两种方法已合并为法，在国外称为PERT/CPM，在国内称为统筹方法（schedulingmethod定义1 件，A,B表示作业。由这种方法画出的网络图称为计划网络图。7计划网络图的基本画法例 某项目工程由11项作业组（分别用代号A,B,,J,K表示其计划完成时2作业流程数据计划完成时间（天计划完成时间（天A5—GB—HC—ID4BJF,G,E4AKF,FC,8图8计划网络 弧的集合，邻接矩阵Wwij)88 (ij)w

A,ij (ij) 18的最长路径，网络模型中有很多求最短路径的算法，为~向图G{VA,W~矩阵Wwij)88 (ij)

ij(ij)计算的程序如下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,:);%从起点sb到终点db的最短各顶点的前驱顶点parent(parent==0)=sbpath0，表示该顶点的前驱是起点mypath=db;t=db;p=parent(t);mypath=[p,mypath];PageRank算法是基于网页分析对关键字匹配搜索结果进行处理的。它借鉴传统引个边，邻接矩阵B(bij)NN，如果从网页i到网页j有超，则bij1，否则为0。 cjbij，ribij 程，其状态转移规律用Markov链描述。定义矩阵A(aij)NN如下a1ddbij，i,j1,2,,N idd0.85A是Markov链的转移概率矩阵，aij表示从页面i转移到页面j的概率。根据Markov链的基本性质，对于正则Markov链存在平稳分布x[x1,,xN]T，满足iNATxx xi1Nx表示在极限状态（转移次数趋于无限）下各网页被的概率分布，将它定义为各网页的PageRank值。假设x已经得到，则它按分量满足方程Nxkaik

(1d)d

xii

1xkk的PageRank值，即网络上所有页面“投票”给网页k的最终值。7N69所示，求它的PageRank219网络结构示意图B和MarkovA

000 000 B A

0

0.0250.0250.8750.025计算得到该Markovx0.2675 0.1323