运筹学第十章 图与网络分析精品文稿.ppt

《运筹学第十章 图与网络分析精品文稿.ppt》由会员分享，可在线阅读，更多相关《运筹学第十章 图与网络分析精品文稿.ppt（43页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、运筹学第十章 图与网络分析第1页，本讲稿共43页 有向图：由点及弧所构成的图，记为D=(V,A)，V,A分别是D的点集合和弧集合。一个方向是从vi指向vj的弧记为(vi,vj)图G或D中的点数记为p(G)或p(D)，边(弧)数记为q(G)(q(D)，简记为p,q。若边e=u,vE，则称u,v为e的端点，也称u,v是相邻的，称e是点u(及点v)的关联边。若在图G中，某个边的两个端点相同，则称e是环。第2页，本讲稿共43页 若两个点之间有多于一条的边，称这些边为多重边。简单图：一个无环，无多重边的图。多重图：一个无环、但允许有多重边的图。给定一个图G=(V,E)，如果图G=(V,E)，使V=V及E

2、E，则称G是G的一个支撑子图。点v的次：以点v为端点边的个数，记为dG(v)或d(v)。悬挂点：次为1的点。悬挂点的关联边称为悬挂边。第3页，本讲稿共43页弧立点：次为零的点。定理1：图G=(V,E)中，所有点的次之和是边数的两倍，即d(v)=2qvV奇点：次为奇数的点。否则称为偶点。定理2：任一图中，奇点的个数为偶数。给定一个图G=(V,E)，一个点边的交错序列(vi1,ei1,vi2,ei2,vik-1,eik-1,vik)，如果满足eit=vit,vit+1(t=1,2,k-1)，则称为一条联结vi1第4页，本讲稿共43页和vik的链，记为(vi1,vi2,vik)，称点vi2,vi3,

3、vik-1为链的中间点。链(vi1,vi2,vik)中，若vi1=vik,，则称之为一个圈，记为(vi1,vi2,vik-1,vi1)。若链(vi1,vi2,vik)中，点vi1,vi2,vik都是不同的，则称之为初等链；若圈(vi1,vi2,vik-1,vi1)中，vi1,vi2,vik-1都是不同的，则称之为初等圈。若链(圈)中含的边均不相同，则称之为简单圈。第5页，本讲稿共43页 连通图：图G中，若任何两个点之间，至少有一条链。连通分图(分图)：若G是不连通图，它的每个连通的部分。基础图：给定一个有向图D=(V,A)，从D中去掉所有弧上的箭头，所得到的无向图。记之为G(D)。给定D中的一

4、条弧a=(u,v)，称u为a的始点，v为a的终点，称弧a是从u指向v的。设(vi1,ai1,vi2,ai2,vik-1,aik-1,vik)是D中的一个点弧交错序列，如果这个序列在基础图G(D)第6页，本讲稿共43页 中所对应的点边序列是一条链，则称这个点弧交错序列是D的一条链。如果(vi1,ai1,vi2,ai2,vik-1,aik-1,vik)是D中的一条链，并且对t=1,2,k-1，均有ait=(vit,vit+1)，称之为从vi1到vik的一条路。若路的第一个点和最后一点相同，则称之为回路。第7页，本讲稿共43页2 树2.1 树及其性质定义1 一个无圈的连通图称为树 定理1 设图G=(

5、V,E)是一个树，p(G)2，则G中至少有两个悬挂点。定理2 图G=(V,E)是一个树的充分必要条件是G中不含圈，且恰有p-1条边。定理3 图G=(V,E)是一个树的充分必要条件是G是连通图，并且q(G)=p(G)-1。定理4 图G是树的充分必要条件是任意两个顶点之间恰有一条链。第8页，本讲稿共43页推论：(1).从一个树中去掉一条边，则余下的图是不连通的。(2).在树中不相邻的两个点间添上一条边，则恰好得到一个圈。2.2图的支撑树 定义2 设图T=(V,E)是图的支撑子图，如果图T=(V,E)是一个树，则称T是G的一个支撑树。定理5：图G有支撑树的充分必要条件是图G是连通的。第9页，本讲稿共

6、43页证必要性：显然。充分性：设图G是连通图，如果G不含圈，那么G本身是一个树，从而G是它自身的一个支撑子图G1。如果G含圈，任取一个圈，从圈中任意地去掉一条边，得到图G的一个支撑子图G1。如果G1不含圈，那么G1是G的一个支撑树(因G1是连通的)；如果G1仍含圈，那么从G1中任取一个圈，从圈中再任意去掉一条边，得到图G的一个支撑子图G2，如此重复，最终可以得到G的一个支撑子图Gk,它不含圈，于是Gk是G的一个支撑树。第10页，本讲稿共43页2.3最小支撑树问题 定义3 给图G=(V,E)，对G中的每一条边vi,vj，相应地有一个数wij，则称这样的图G为赋权图，wij称为边vi,vj上的权。

7、设有一个连通图G=(V,E)，每一边e=(vi,vj)有一个非负权w(e)=wij(wij0)定义4:如果T=(V,E)是G的一个支撑树，称E中所有边的权之和为支撑树T的权，记为w(T)，即 w(T)=wij (vi,vj)T第11页，本讲稿共43页如果支撑树T*的权w(T*)是G的所有支撑树的权中最小者，则称T*是G的最小支撑树(简称最小树)w(T*)=min w(T)T 求最小树的方法：方法一(避圈法)开始选一条最小权的边，以后每一步中，总从未被选取的边中选一条权最小的边，并使之与已选取的边不构成圈。第12页，本讲稿共43页 方法二(破圈法)任取一个圈，从圈中去掉一条权最大的边。在余下的图

8、中，重复这个步骤，一直到一个不含圈的图为止，这时的图便是最小树。例 用破圈法求下图的最小树12222312222333445第13页，本讲稿共43页3 最短路问题 Dijkstra算法的基本思想：若vs,v1,vk是从vs到vk的最短路，则vs,v1,vi是从vs到vi的最短路。T(临时)标号：从vs到某一节点最短距离的上界。P(永久)标号：从vs到某一节点的最短距离。第14页，本讲稿共43页步骤：给vs标上永久标号P(vs)=0，其余节点标上临时标号T(vj)=(1)若节点vi是刚得到P标号的点。把与vi有弧(边)直接相连而且有属于T标号的节点，改为下列T标号T(vj)=minT(vj),P

9、(vi)+dij (2)把T标号中标号最小的节点vj0的临时标号T(vj0)改为P(vj0),直至算法终止;否则转(1)第15页，本讲稿共43页例 求节点v1到节点v5的最短距离及其路线vSv1v2v3v4v5122233344解 P(vs)=0 T(vj)=,j=1,5第一步：T(v1)=minT(v1),P(vs)+ds1=min,0+4=4 (1)与节点vs直接相连的临时标号的节点为 v1,v2，将这两个节点的临时标号改为第16页，本讲稿共43页T(v2)=minT(v2),P(vs)+ds2=min,0+3=3 (2)在所有T标号中，最小的为T(v2)=3,于是令P(v2)=3第二步：

10、(1)与节点v2直接相连的临时标号的节点为v3和v4，把这两个节点的T标号改为T(v1)=minT(v1),P(v2)+d21=min4,3+2=4T(v4)=minT(v4),P(v2)+d24=min,3+2=5 (2).在所有T变化中，T(v1)=4最小，于是令P(v1)=4第17页，本讲稿共43页第三步：(1).与节点v1相连的临时标号的节点为v3,v4，把这两个节点的T标号改为T(v3)=minT(v3),P(v1)+d13=min,4+3=7T(v4)=minT(v4),P(v1)+d14=min5,4+1=5 (2).在T标号中，T(v4)=5最小，令P(v4)=5第四步：(1)

11、.与节点v4相连的T标号有v3,v5把这两个节点的T标号改为第18页，本讲稿共43页T(v3)=minT(v3),P(v4)+d43=min7,5+2=7T(v5)=minT(v5),P(v5)+d45=min,5+4=9 (2).T(v3)最小,P(v3)=7第五步：(1).与v3相连的临时标号有v5T(v5)=minT(v5),P(v3)+d35=min9,7+3=9(2).P(v5)=9最短路线：vsv1v4 v5 vsv2v4 v5第19页，本讲稿共43页 下面介绍当赋权有向图中，存在具负权的弧时，求最短路的方法。令d(1)(vs,vj)=wsj对t=2,3,d(t)(vs,vj)=m

12、ind(t-1)(vs,vi)+wij(j=1,2,p)若进行到某一步,例如第k步,对所有j=1,2,p,有d(k)(vs,vj)=d(k-1)(vs,vj)i第20页，本讲稿共43页则d(k)(vs,vj)j=1,2,p即为到各点的最短路的权。例 求下图所示有向图中从v1到各点的最短路。v1v4v2v3v5v6v7v825-34674-23-1-342第21页，本讲稿共43页 wij d(t)(v1,vj)v1 v2 v3 v4 v5 v6 v7 v8v1v2 v3 v4v5v6v7v8025-30-2406400-30720320t=1 t=2 t=3 t=4 t=5 t=6025-302

13、0-3611020-36615020-3361410020-336910020-336910说明：表中空格处为+。第22页，本讲稿共43页例 设备更新问题制订一设备更新问题，使得总费用最小 第1年 第2年 第3年 第4年 第5年 购买费 13 14 16 19 24 使用年数 0-1 1-2 2-3 3-4 4-5 维修费 8 10 13 18 27 解设以vi(i=1,2,3,4,5)表示“第i年初购进一台新设备”这种状态，以v6表示“第5年末”这种状态；以弧(vi,vj)表示“第i年初购置的一台设备一直使用到第j年初”这一方案，以wij表示这一方案所需购置费和维护费之和。第23页，本讲稿共

14、43页这样，可建立本例的网络模型。于是，该问题就可归结为从图中找出一条从v1到v6的最短路问题。用Dijkstra标号法，求得最短路为 v1v3v6 即第一年初购置的设备使用到第三年初予以更新，然后一直使用到第五年末。这样五年的总费用最少，为78。第24页，本讲稿共43页v1v2v3v5v6v4214432228962316345244734273732(0)(21)(31)(44)(62)(78)第25页，本讲稿共43页4 最大流问题 如下是一运输网络，弧上的数字表示每条弧上的容量，问：该网络的最大流量是多少？vsv2v1v3v4vt432312234第26页，本讲稿共43页4.1 基本概念

15、和基本定理(1)网络与流 定义1 给定一个有向图D=(V,A),在V中有一个发点vs和一收点vt，其余的点为中间点。对于每一条弧(vi,vj),对应有一个c(vi,vj)0,(cij)称为弧的容量。这样的有向图称为网络。记为D=(V,A,C)。网络的流：定义在弧集合A上的一个函数f=f(vi,vj)，称f(vi,vj)为弧(vi,vj)上的流量。(fij)第27页，本讲稿共43页(2)可行流与最大流定义2 满足下列条件的流称为可行流：1)0 fijcij2)对于每一is,t fij=fji(vi,vj)A(vj,vi)A对于发点vs和收点vt，fsj fjs=v(f)(vs,vj)A(vj,v

16、s)A第28页，本讲稿共43页 ftj fjt=v(f)(vt,vj)A(vj,vt)A式中v(f)称为这个可行流的流量，即发点的净输出量（或收点的净输入量）。最大流问题：求一流fij满足0 fijcij v(f)i=sfijfji=0 is，t v(f)i=t且使v(f)达到最大。第29页，本讲稿共43页(3)增广链 给定可行流f=fij，使fij=cij的弧称为饱和弧，使fij0的弧称为非零流弧。若是网络中连接发点vs和收点vt的一条链，定义链的方向是从vs到vt，则链上的弧被分成两类：前向弧：弧的方向与链的方向一致 全体+后向弧：弧的方向与链的方向相反 全体第30页，本讲稿共43页 定义

17、3 设f是一可行流，是从vs到vt的一条链，若满足下列条件，则称之为（关于流f的）一条增广链：在弧(vi,vj)+上，0fijcij 在弧(vi,vj)上，0fijcij(4)截集与截量 设S，TV，ST=，我们把始点在S，终点在T中的所有弧构成的集合，记为（S，T）。定义4 给定网络D=(V,A,C)，若点集V被剖分为两个非空集合V1和V1，使vsV1，第31页，本讲稿共43页vtV1，则把弧集(V1,V1)称为是（分离vs和vt的）截集。截集是从vs到vt的必经之路。定义5 给定一截集(V1,V1)，把截集(V1,V1)中所有弧的容量之和称为这个截集的容量(截量),记为C(V1,V1)。v

18、(f)C(V1,V1)若对于一可行流f*，网络中有一截集(V1*,V1*)，使得v(f*)=C(V1*,V1*)，则f必是最大流，而(V1*,V1*)，必定是容量最小的截集，即最小截集。第32页，本讲稿共43页 定理1 可行流f*是最大流的充要条件是不存在关于f*的最大流。若f*是最大流，则网络中必存在一个截集(V1*,V1*)，使得 v(f*)=C(V1*,V1*)定理2 任一网络D中，从vs到vt的最大流的流量等于分离vs，vt的最小截集的截量。4.2 寻找最大流的标号法(Ford Fulkerson)思想：从一可行流出发，检查关于此流是否存在增广链。若存在增广链，则增大流第33页，本讲稿

19、共43页量，使此链变为非增广链；这时再检查是非还有增广链，若还有，继续调整，直至不存在增广链为止。过程：1)标号过程 标号过程开始时，总先给vs标上(0,+),这时vs是标号而未检查的点，其余都是未标号的点。一般，取一个标号而未检查的点vi，对一切未标号的点vj；(1)若在弧(vi,vj)上，fij0，则给vj标号(vi,l(vj)，这里l(vj)=minl(vi)，fji。这时点vj成为标号而未检查的点。于是vi成为标号而已检查过的点。重复上述步骤，一旦vt被标上号，表明得到一条从vs到vt的增广链，转入调整阶段。若所有标号都已检查过，而标号过程进行不下去，则算法结束，这时的可行流就是最大流

20、。第35页，本讲稿共43页 2)调整过程 首先按及其它点的第一个标号，利用“反向追踪”的方法，找出增广链。令调整量为=l(vt)令 fij+(vi,vj)+fij=fij (vi,vj)fij (vi,vj)去掉所有的标号，对新的可行流f=fij，重新进入标号过程。v(f)=v(f)+第36页，本讲稿共43页可结合下图理解其实际涵义。vsv1v2v3v4vt(4,4)(8,1)(4,3)(2,2)(4,0)(2,2)(1,1)(7,2)(9,2)第37页，本讲稿共43页vsv1vtv4v2v3(9,7)(5,3)(3,2)(4,4)(5,5)(3,1)(2,1)(6,3)(7,7)例 求下列网

21、络的最大流与最小截集。解一、标号过程（1）先给vs标上(0,+)。（2）检查vs,在弧(vs,v1)上,fs1=7,cs1=9,fs1cs1,则v1的标号为(vs,l(v1)，其中第38页，本讲稿共43页l(v1)=minl(vs)，cs1fs1=min+，9 2=2（3）检查v1,在弧(v1,v4)上,f14=7,c14=9,f140，则v3的标号为(-v4,l(v3)，其中l(v3)=minl(v4)，f34=min2，1=1（5）检查v3,在弧(v3,vt)上,f3t=3,c3t=6,f3tc3t,第39页，本讲稿共43页则vt的标号为(v3,l(vt)，其中l(vt)=minl(v3)

22、，c3tf3t=min1，6-3=1这样，我们得到了一增广链,如图所示。vsv1vtv4v2v3(9,7)(5,3)(3,2)(4,4)(5,5)(3,1)(2,1)(6,3)(7,7)(0,)(vs,2)(v1,2)(-v4,1)(v3,1)第40页，本讲稿共43页其中+=(vs,v1),(v1,v4),(v3,vt)，=(v3,v4)二、调整过程取调整量为=1，在上调整f。在+上：fs1+=7+1=8 f14+=2+1=3 f4t+=5+1=6在上：f43=11=0其余弧上的流量不变，这样得到一个新的流，如下图所示。第41页，本讲稿共43页 在上图中重复上述标号过程，依次给vs,v2,v1,v4标号后，由于标号无法继续下去，算法结束。这时的流为最大流，最大流的流量为vsv1vtv4v2v3(9,8)(5,3)(3,2)(4,4)(5,5)(3,2)(2,0)(6,4)(7,7)v(f)=8+3=11第42页，本讲稿共43页 与此同时，可找到最小截集(V1,V1)，其中V1为标号点集合，V1为未标号点集合，弧集合(V1,V1)即为最小截集。此例中，V1=vs,v2,v1,v4,V1=v3,vt,(V1,V1)=(v1,v3)，(v4,vt)第43页，本讲稿共43页