matlab图论方法.ppt

,单击此处编辑母版标题样式,*,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,6,图论方法,什么是图,?,A,B,C,D,哥尼斯堡七桥示意图,问题,1(,哥尼斯堡七桥,问题,):,能否从任一陆地出发通过每座桥恰好一次而回到出发点？,1,A,B,D,C,七桥问题模拟图,欧拉指出：,如果每块陆地所连接的桥都是偶数座，则从任一陆地出发，必能通过每座桥恰好一次而回到出发地,.,2,问题,2(,哈密顿环球旅行,问题,):,十二面体的,20,个顶点代表世界上,20,个城市，能否从某个城市出发在十二面体上依次经过每个城市恰好一次最后回到出发点？,哈密顿圈（环球旅行游戏）,3,问题,3(,四色问题,):,对任何一张地图进行着色，两个共同边界的国家染不同的颜色，则只需要四种颜色就够了,.,问题,4(,关键路径问题,):,一项工程任务,大到建造一座大坝,一座体育中心,小至组装一台机床,一架电视机,都要包括许多工序,.,这些工序相互约束,只有在某些工序完成之后,一个工序才能开始,.,即它们之间存在完成的先后次序关系,一般认为这些关系是预知的,而且也能够预计完成每个工序所需要的时间,.,这时工程领导人员迫切希望了解最少需要多少时间才能够完成整个工程项目,影响工程进度的要害工序是哪几个？,4,6.1,图论的基本概念,图论中的,“,图,”,并不是通常意义下的几何图形或物体的形状图,而是以一种抽象的形式来表达一些确定的事物之间的联系的一个数学系统,.,定义,1,一个有序二元组,(,V,E,),称为一个,图,记为,G,=(,V,E,),其中,V,称为,G,的顶点集,V,其元素称为,顶点,或,结点,简称,点,;,E,称为,G,的边集,其元素称为,边,它联结,V,中的两个点,如果这两个点是无序的,则称该边为,无向边,否则,称为,有向边,.,如果,V,=,v,1,v,2,v,n,是有限非空点集,则称,G,为,有限图,或,n,阶图,.,5,如果,E,的每一条边都是无向边,则称,G,为,无向图,(,如图,1),;,如果,E,的每一条边都是有向边,则称,G,为,有向图,(,如图,2),;,否则,称,G,为,混合图,.,图,1,图,2,并且常记,V,=,v,1,v,2,v,n,|,V,|,=,n,;,E,=,e,1,e,2,e,m,(,e,k,=,v,i,v,j,),|,E,|,=,m,.,称点,v,i,v,j,为边,v,i,v,j,的,端点,.,在有向图中,称点,v,i,v,j,分别为边,v,i,v,j,的,始点,和,终点,.,6,对于一个图,G,=(,V,E,),人们常用图形来表示它,称其为,图解,.,凡是有向边,在图解上都用箭头标明其方向,.,例如,设,V,=,v,1,v,2,v,3,v,4,E,=,v,1,v,2,v,1,v,3,v,1,v,4,v,2,v,3,v,2,v,4,v,3,v,4,则,G,=(,V,E,),是一个有,4,个顶点和,6,条边的图,G,的图解如下图所示,.,7,一个图会有许多外形不同的图解,下面两个图表示同一个图,G,=(,V,E,),的图解,.,其中,V,=,v,1,v,2,v,3,v,4,E,=,v,1,v,2,v,1,v,3,v,1,v,4,v,2,v,3,v,2,v,4,v,3,v,4,.,今后将不计较这种外形上的差别,而用一个容易理解的、确定的图解去表示一个图,.,8,有边联结的两个点称为,相邻的点,有一个公共端点的边称为,相邻边,.,边和它的端点称为,互相关联,.,常用,d,(,v,),表示图,G,中与顶点,v,关联的边的数目,d,(,v,),称为顶点,v,的,度数,.,用,N,(,v,),表示图,G,中所有与顶点,v,相邻的顶点的集合,.,d,(,v,1,)=,d,(,v,3,)=,d,(,v,4,)=4,d,(,v,2,)=2.,9,我们今后只讨论,有限简单图,：,(1),顶点个数是有限的,;,(2),任意一条边有且只有两个不同的点与它相互关联,;,(3),若是无向图,则任意两个顶点最多只有一条边与之相联结,;,(4),若是有向图,则任意两个顶点最多只有两条边与之相联结,.,当两个顶点有两条边与之相联结时，这两条边的方向相反,.,如果某个有限图不满足,(2)(3)(4),可在某条边上增设顶点使之满足,.,10,定义,2,若将图,G,的每一条边,e,都对应一个实数,F,(,e,),则称,F,(,e,),为该边的,权,并称图,G,为,赋权图,(,网络,),记为,G,=(,V,E,F,),.,定义,3,设,G,=(,V,E,),是一个图,v,0,v,1,v,k,V,且,1,i,k,v,i,-,1,v,i,E,则称,v,0,v,1,v,k,是,G,的一条,通路,.,如果通路中没有相同的边,则称此通路为,道路,.,始点和终点相同的道路称为,圈,或,回路,.,如果通路中既没有相同的边,又没有相同的顶点,则称此通路为,路径,简称,路,.,定义,4,任意两点均有通路的图称为,连通图,.,定义,5,连通而无圈的图称为,树,常用,T,表示树,.,11,例,一摆渡人欲将一只狼,一头羊,一篮菜从河西渡过河到河东,.,由于船小,一次只能带一物过河，并且狼与羊,羊与菜不能独处,.,给出渡河方法,.,解,：用四维,0-1,向量表示,(,人,狼,羊,菜,),在河西岸的状态,(,在河西岸则分量取,1,否则取,0),共有,2,4,=16,种状态,.,在河东岸的状态类似记作,.,由题设,状态,(0,1,1,0),(0,0,1,1),(0,1,1,1),是不允许的,从而对应状态,(1,0,0,1),(1,1,0,0),(1,0,0,0),也是不允许的,.,以可,允许的,10,个,状态,向量作为顶点,将可能互相转移的状态用线段连接起来构成一个图,.,根据此图便可找到,渡河方法,.,12,(1,1,1,1),(1,1,1,0),(1,1,0,1),(1,0,1,1),(1,0,1,0),(0,0,0,0),(0,0,0,1),(0,0,1,0),(0,1,0,0),(0,1,0,1),(0,1,0,1),(0,1,0,0),(0,0,1,0),(0,0,0,1),(0,0,0,0),(1,0,1,0),(1,0,1,1),(1,1,0,1),(1,1,1,0),(1,1,1,1),河西,=(,人,狼,羊,菜,),河东,=(,人,狼,羊,菜,),将,10,个顶点分别记为,A,1,A,2,A,10,则,渡河问题化为在该图中求一条从,A,1,到,A,10,的,路,.,从图中易得到两条,路,：,A,1,A,6,A,3,A,7,A,2,A,8,A,5,A,10,;,A,1,A,6,A,3,A,9,A,4,A,8,A,5,A,10,.,13,图的矩阵表示,邻接矩阵 邻接矩阵表示了点与点之间的邻接关系,.,一个,n,阶图,G,的邻接矩阵,A,=(,a,ij,),n,n,其中,14,无向图,G,的邻接矩阵,A,是一个对称矩阵,.,权矩阵,一个,n,阶赋权图,G,=(,V,E,F,),的权矩阵,A,=(,a,ij,),n,n,其中,有限简单图基本上可用权矩阵来表示,.,15,无向图,G,的权矩阵,A,是一个对称矩阵,.,16,关联矩阵 一个有,m,条边的,n,阶有向图,G,的关联矩阵,A,=(,a,ij,),n,m,其中,若,v,i,是,e,j,的始点,;,若,v,i,是,e,j,的终点,;,若,v,i,与,e,j,不关联,.,有向图的关联矩阵每列的元素中有且仅有一个,1,有且仅有一个,-,1.,17,一个有,m,条边的,n,阶无向图,G,的关联矩阵,A,=(,a,ij,),n,m,其中,若,v,i,与,e,j,关联,;,若,v,i,与,e,j,不关联,.,无向图的关联矩阵每列的元素中有且仅有两个,1.,18,6.2,最短路与最小生成树,定义,1,设,P,(,u,v,),是赋权图,G,=(,V,E,F,),中从点,u,到,v,的路径,用,E,(,P,),表示路径,P,(,u,v,),中全部边的集合,记,则称,F,(,P,),为路径,P,(,u,v,),的,权,或,长度,(,距离,),.,定义,2,若,P,0,(,u,v,),是,G,中连接,u,v,的路径,且对任意在,G,中连接,u,v,的路径,P,(,u,v,),都有,F,(,P,0,),F,(,P,),则称,P,0,(,u,v,),是,G,中连接,u,v,的,最短路,.,19,重要性质：,若,v,0,v,1,v,m,是,图,G,中从,v,0,到,v,m,的最短路,则,1,k,m,v,0,v,1,v,k,必为,G,中从,v,0,到,v,k,的最短路,.,即：最短路是一条路，且最短路的任一段也是最短路,.,求非负赋权图,G,中某一点到其它各点最短路，一般用,Dijkstra,标号算法；求非负赋权图上任意两点间的最短路，一般用,Floyd,算法,.,这两种算法均适用于有向非负赋权图,.,由于,Dijkstra,标号算法较为复杂，以下只介绍,Floyd,算法,.,20,求赋权图中任意两点的最短路的,Floyd,算法：,设,A,=(,a,ij,),n,n,为赋权图,G,=(,V,E,F,),的权矩阵,d,ij,表示从,v,i,到,v,j,点的距离,r,ij,表示从,v,i,到,v,j,点的最短路中一个点的编号,.,赋初值,.,对所有,i,j,d,ij,=,a,ij,r,ij,=,j,.,k,=1.,转向,.,更新,d,ij,r,ij,.,对所有,i,j,若,d,ik,+,d,k j,d,ij,则令,d,ij,=,d,ik,+,d,kj,r,ij,=,k,转向,;,终止判断,.,若,k,=,n,终止,;,否则令,k,=,k,+1,转向,.,最短路线可由,r,ij,得到,.,21,例,1,求下图中任意两点间的最短路,(P145,图,6-5).,22,解,：用,Floyd,算法,首先写出其,(,对称的,),权矩阵,A,=(,a,ij,),8,8,，然后利用计算机编程计算,.,0 1 2 3 4 5 6 7,0,0 2 8 1 ,1,2 0 6 1 ,2,8 6 0 7 5 1 2,3,1 7 0 9,4,1 5 0 3 8,5,1 3 0 4 6,6,2 9 4 0 3,7,8 6 3 0,23,以下仅从图上进行直观操作,.,根据若,d,ik,+,d,kj,d,ij,则令,d,ij,=,d,ik,+,d,kj,.,将原来的,赋权值改变为,|,v,2,v,4,|=4,|,v,5,v,6,|=3,.,再依次改变为,|,v,1,v,2,|=5,|,v,0,v,2,|=7,.,接下来根据,若,d,ij,=,d,ik,+,d,kj,则删除,v,i,到,v,j,的连线,.,得到,24,从上图中容易得到任意两点间的最短路,.,例如,v,1,到,v,6,的路有三条：,v,1,v,0,v,3,v,2,v,6,(,长度为,12),v,1,v,4,v,5,v,2,v,6,(,长度为,7),v,1,v,4,v,7,v,6,(,长度为,12).,25,设备更新问题,某企业每年年初,都要作出决定,如果继续使用旧设备,要付维修费；若购买一台新设备,要付购买费,.,试制定一个,5,年更新计划,使总支出最少,.,已知设备在每年年初的购买费分别为,11,11,12,12,13.,使用不同时间设备所需的维修费分别为,5,6,8,11,18.,解,设,b,i,表示设备在第,i,年年初的购买费,c,i,表示设备使用,i,年后的维修费,V,=,v,1,v,2,v,6,点,v,i,表示第,i,年年初购进一台新设备,虚设一个点,v,6,表示第,5,年年底,.,E,=,v,i,v,j,|1,i,j,6,.,26,这样上述设备更新问题就变为：在有向赋权图,G,=(,V,E,F,)(,图解如下,),中求,v,1,到,v,6,的最短路问题,.,27,由实际问题可知,设备使用三年后应当更新,因此删除该图中,v,1,到,v,5,v,1,到,v,6,v,2,到,v,6,的连线；又设备使用一年后就更新则不划算,因此再删除该图中,v,1,v,2,v,2,v,3,v,3,v,4,v,4,v,5,v,5,v,6,五条连线后得到,从上图中容易得到,v,1,到,v,6,只有两条路：,v,1,v,3,v,6,和,v,1,v,4,v,6,.,而这两条路都是,v,1,到,v,6,的最短路,.,28,最小生成树,由树的定义不难知道,任意一个连通的,p,q,图,(,p,个顶点,q,条边,),G,适当去掉,q,-,p,+1,条边后,都可以变成树,这棵树称为图,G,的,生成树,.,设,T,是图,G,的一棵生成树,用,F,(,T,),表示树,T,中所有边的权数之和,F,(,T,),称为,树,T,的权,.,一个连通图,G,的生成树一般不止一棵,图,G,的所有生成树中权数最小的生成树称为图,G,的,最小生成树,.,求最小生成树问题有很广泛的实际应用,.,例如,把,n,个乡镇用高压电缆连接起来建立一个电网,使所用的电缆长度之和最短,即费用最小,就是一个求最小生成树问题,.,29,求连通图,G,的最小生成树,T,的算法,(,Kruskal,避圈法,),：将图,G,中的边按权从小到大逐条考察,按不构成圈的原则加入到,T,中,直到,q,(,T,)=,p,(,G,),-,1,为止,.,例如右图,其中,p,(,G,)=8.,其最小生成树如下：,类似地,可定义连通图,G,的最大生成树,.,30,选址问题,现准备,在,n,个,居民点,v,1,v,2,v,n,中设置一银行,.,问设在哪个点,可使最大服务距离最小,?,若设置两个银行,问设在哪两个点,?,模型假设,假设各,个,居民点都有条件设置银行,并有路相连,且路长已知,.,模型建立与求解,用,Floyd,算法求出任意两,个,居民点,v,i,v,j,之间的最短距离,并用,d,ij,表示,.,设置一个银行,银行设,在,v,i,点,的最大服务距离为,31,求,k,使,即若设置一个银行,则银行设在,v,k,点,可使最大服务距离最小,.,设置两个银行,假设银行设,在,v,s,v,t,点,使最大服务距离最小,.,记,则,s,t,满足：,进一步,若设置多个银行呢？,32,6.3,二部图的匹配及其应用,定义,1,设,X,Y,都是非空有限集,且,X,Y,=,E,xy,|,x,X,y,Y,称,G,=(,X,Y,E,),为,二部图,.,二部图可认为是有限简单无向图,.,如果,X,中的每个点都与,Y,中的每个点邻接,则称,G,=(,X,Y,E,),为,完备二部图,.,若,F,：,E,R,+,则称,G,=(,X,Y,E,F,),为,二部赋权图,.,二部赋权图的权矩阵一般记作,A,=(,a,ij,),|,X,|,Y,|,其中,a,ij,=,F,(,x,i,y,j,),.,33,定义,2,设,G,=(,X,Y,E,),为二部图,且,M,E,.,若,M,中任意两条边在,G,中均不邻接,则称,M,是,二部图,G,的一个,匹配,.,定义,3,设,M,是二部图,G,的一个匹配,如果,G,的每一个点都是,M,中边的顶,点,则称,M,是二部图,G,的,完美匹配,；,如果,G,中没有另外的匹配,M,0,使,|,M,0,|,|,M,|,则称,M,是二部图,G,的,最大匹配,.,在二部赋权图,G,=(,X,Y,E,F,),中,权数最大的最大匹配,M,称为二部赋权图,G,的,最佳匹配,.,显然,每个完美匹配都是最大匹配,反之不一定成立,.,34,工作安排问题之一,给,n,个工作人员,x,1,x,2,x,n,安排,n,项工作,y,1,y,2,y,n,.,n,个工作人员中每个人能胜任一项或几项工作,但并,不是所有工作人员都能从事任何一项工作,.,比如,x,1,能做,y,1,y,2,工作,x,2,能做,y,2,y,3,y,4,工作等,.,这样便提出一个问题,对所有的工作人员能不能都分配一件他所能胜任的工作？,我们构造一个二部图,G,=(,X,Y,E,),这里,X,=,x,1,x,2,x,n,Y,=,y,1,y,2,y,n,并且当且仅当工作人员,x,i,胜任工作,y,j,时,x,i,与,y,j,才相邻,.,于是,问题转化为求二部图的一个完美匹配,.,因为,|,X,|=|,Y,|,所以完美匹配即为最大匹配,.,35,求二部图,G,=(,X,Y,E,),的最大匹配算法,(,匈牙利算法,P149),迭代步骤,:,从,G,的任意匹配,M,开始,.,将,X,中,M,的所有,非饱和点,都给以标号,0,和标记*,转向,.,M,的非饱和点即非,M,的某条边的顶点,.,若,X,中所有有标号的点都已去掉了标记*,则,M,是,G,的最大匹配,.,否则任取,X,中一个既有标号又有标记*的点,x,i,去掉,x,i,的标记*,转向,.,找出在,G,中所有与,x,i,邻接的点,y,j,若所有这样的,y,j,都已有标号,则转向,否则转向,.,36,对与,x,i,邻接且尚未给标号的,y,j,都给定标号,i,.,若所有的,y,j,都是,M,的,饱和点,则转向,否则逆向返回,.,即由其中,M,的任一个非饱和点,y,j,的标号,i,找到,x,i,再由,x,i,的标号,k,找到,y,k,最后由,y,t,的标号,s,找到标号为,0,的,x,s,时结束,获得,M,-,增广路,x,s,y,t,x,i,y,j,记,P,=,x,s,y,t,x,i,y,j,重新记,M,为,M,P,转向,.,不必理会,M,-,增广路,的定义,.,M,P,=,M,P,M,P,是对称差,.,将,y,j,在,M,中与之邻接的点,x,k,给以标号,j,和标记,*,转向,.,37,例 求下图所示二部图,G,的最大匹配,.,解 取初始匹配,M,0,=,x,2,y,2,x,3,y,3,x,5,y,5,(,上图粗线所示,).,给,X,中,M,0,的两个非饱和点,x,1,x,4,都给以标号,0,和标记*,(,如下图所示,).,38,给,X,中,M,0,的两个非饱和点,x,1,x,4,都给以标号,0,和标记*,(,如下图所示,).,去掉,x,1,的标记,*,将与,x,1,邻接的两个点,y,2,y,3,都给以标号,1.,因为,y,2,y,3,都是,M,0,的两个饱和点,所以将它们在,M,0,中邻接的两个点,x,2,x,3,都给以相应的标号和标记,*,(,如下图所示,).,39,去掉,x,1,的标记,*,将与,x,1,邻接的两个点,y,2,y,3,都给以标号,1.,因为,y,2,y,3,都是,M,0,的两个饱和点,所以将它们在,M,0,中邻接的两个点,x,2,x,3,都给以相应的标号和标记,*,(,如下图所示,).,去掉,x,2,的标记,*,将与,x,2,邻接且尚未给标号的三个点,y,1,y,4,y,5,都给以标号,2(,如下图所示,).,40,去掉,x,2,的标记,*,将与,x,2,邻接且尚未给标号的三个点,y,1,y,4,y,5,都给以标号,2(,如下图所示,).,因为,y,1,是,M,0,的非饱和点,所以顺着标号逆向返回依次得到,x,2,y,2,直到,x,1,为,0,为止,.,于是得到,M,0,的增广路,x,1,y,2,x,2,y,1,记,P,=,x,1,y,2,y,2,x,2,x,2,y,1,.,取,M,1,=,M,0,P,=,x,1,y,2,x,2,y,1,x,3,y,3,x,5,y,5,则,M,1,是比,M,多一边的匹配,(,如下图所示,).,41,因为,y,1,是,M,0,的非饱和点,所以顺着标号逆向返回依次得到,x,2,y,2,直到,x,1,为,0,为止,.,于是得到,M,0,的增广路,x,1,y,2,x,2,y,1,记,P,=,x,1,y,2,y,2,x,2,x,2,y,1,.,取,M,1,=,M,0,P,=,x,1,y,2,x,2,y,1,x,3,y,3,x,5,y,5,则,M,1,是比,M,多一边的匹配,(,如下图所示,).,42,再给,X,中,M,1,的非饱和点,x,4,给以标号,0,和标记,*,然后去掉,x,4,的标记,*,将与,x,4,邻接的两个点,y,2,y,3,都给以标号,4.,因为,y,2,y,3,都是,M,1,的两个饱和点,所以将它们在,M,1,中邻接的两个点,x,1,x,3,都给以相应的标号和标记,*,(,如下图所示,).,43,去掉,x,1,的标记,*,因为与,x,1,邻接的两个点,y,2,y,3,都有标号,4,所以去掉,x,3,的标记,*,.,而与,x,3,邻接的两个点,y,2,y,3,也都有标号,4,此时,X,中所有有标号的点都已去掉了标记,*,(,如下图所示,),因此,M,1,是,G,的最大匹配,.,G,不存在饱和,X,的每个点的匹配,当然也不存在完美匹配,.,44,工作安排问题之二,给,n,个工作人员,x,1,x,2,x,n,安排,n,项工作,y,1,y,2,y,n,.,如果每个工作人员工作效率不同,要求工作分配的同时考虑总效率最高,.,我们构造一个二部赋权图,G,=(,X,Y,E,F,),这里,X,=,x,1,x,2,x,n,Y,=,y,1,y,2,y,n,F,(,x,i,y,j,),为工作人员,x,i,胜任工作,y,j,时的工作效率,.,则问题转化为：求二部赋权图,G,的最佳匹配,.,在求,G,的最佳匹配时,总可以假设,G,为完备二部赋权图,.,若,x,i,与,y,j,不相邻,可令,F,(,x,i,y,j,)=0.,同样地,还可虚设点,x,或,y,使,|,X,|=|,Y,|,.,如此就将,G,转化为完备二部赋权图,而且不会影响结果,.,45,定义,设,G,=,(,X,Y,E,F,),为完备的二部赋权图,若,L,：,X,Y,R,+,满足：,x,X,y,Y,L,(,x,)+,L,(,y,),F,(,xy,),则称,L,为,G,的一个,可行点标记,记相应的生成子图为,G,L,=,(,X,Y,E,L,F,),这里,E,L,=,xy,E,|,L,(,x,)+,L,(,y,)=,F,(,xy,),.,求完备二部赋权图,G,=(,X,Y,E,F,),的最佳匹配算法迭代步骤,(P152),：,设,G,=,(,X,Y,E,F,),为完备的二部赋权图,L,是其一个初始可行点标记,通常取,L,(,x,)=max,F,(,x y,)|,y,Y,x,X,L,(,y,)=0,y,Y,.,46,M,是,G,L,的一个匹配,.,若,X,的每个点都是饱和的,则,M,是最佳匹配,.,否则取,M,的非饱和点,u,X,令,S,=,u,T,=,转向,.,记,N,L,(,S,)=,v,|,u,S,uv,G,L,.,若,N,L,(,S,)=,T,则,G,L,没有完美匹配,转向,.,否则转向,.,调整标记,计算,a,L,=min,L,(,x,)+,L,(,y,),-,F,(,xy,)|,x,S,y,Y,T,.,由此得新的可行点标记,令,L,=,H,G,L,=,G,H,重新给出,G,L,的一个匹配,M,转向,.,47,取,y,N,L,(,S,),T,若,y,是,M,的饱和点,转向,.,否则,转向,.,设,x y,M,则令,S,=,S,x,T,=,T,y,转向,.,在,G,L,中的,u,-,y,路是,M,-,增广路,设为,P,并令,M,=,M,P,转向,.,48,6.4,网络流问题,定义,1,设,G,=(,V,E,),为有向图,在,V,中指定一点称为,发点,(,记为,v,s,),和另一点称为,收点,(,记为,v,t,),其余点叫做中间点,.,对每一条边,v,i,v,j,E,对应一个非负实数,C,ij,称为它的,容量,.,这样的,G,称为,容量网络,简称,网络,记作,G,=(,V,E,C,),.,定义,2,网络,G,=(,V,E,C,),中任一条边,v,i,v,j,有流量,f,ij,称集合,f,=,f,ij,为网络,G,上的一个,流,.,满足下述条件的流,f,称为,可行流,：,(,限制条件,),对每一边,v,i,v,j,有,0,f,ij,C,ij,;,(,平衡条件,),对于中间点,v,k,有,f,ik,=,f,kj,即中间点,v,k,的输入,量,=,输出,量,.,49,如果,f,是可行流,则对收、发点,v,t,、,v,s,有,f,si,=,f,jt,=,W,f,即从,v,s,点发出的物质总量,=,v,t,点输入的量,.,W,f,称为网络流,f,的总流量,.,上述概念可以这样来理解,如,G,是一个运输网络,则发点,v,s,表示发送站,收点,v,t,表示接收站,中间点,v,k,表示中间转运站,可行流,f,ij,表示某条运输线上通过的运输量,容量,C,ij,表示某条运输线能承担的最大运输量,W,f,表示运输总量,.,可行流总是存在的,.,比如所有边的流量,f,ij,=0,就是一个可行流,(,称为零流,).,50,所谓,最大流问题,就是在容量网络中,寻找流量最大的可行流,.,求最大可行流的算法,(,不必理会其中,可增广链,的定义,),见,P155-156.,实际问题中,一个网络会出现下面两种情况：,发点和收点都不止一个,.,解决的方法是再虚设一个发点,v,s,和一个收点,v,t,发点,v,s,到所有原发点边的容量都设为无穷大,所有原收点到收点,v,t,边的容量都设为无穷大,.,网络中除了边有容量外,点也有容量,.,解决的方法是将所有有容量的点分成两个点,如点,v,有容量,C,v,将点,v,分成两个点,v,和,v,令,C,(,vv,)=,C,v,.,51,最小费用流问题,这里我们要进一步探讨不仅要使网上的流达到最大,或者达到要求的预定值,而且还要使运输流的费用是最小的,这就是最小费用流问题,.,最小费用流问题的一般提法：,已知网络,G,=(,V,E,C,),每条边,v,i,v,j,E,除了已给容量,C,ij,外,还给出了单位流量的费用,b,ij,(,0,).,所谓最小费用流问题就是求一个总流量已知的可行流,f,=,f,ij,使得总费用,最小,.,52,特别地,当要求,f,为最大流时,此问题即为,最小费用最大流问题,.,设网络,G,=(,V,E,C,),取初始可行流,f,为零流,求解最小费用流问题的迭代步骤,(P158-159),：,构造有向赋权图,G,f,=,(,V,E,f,F,),对于任意的,v,i,v,j,E,E,f,F,的定义如下：,当,f,ij,=0,时,v,i,v,j,E,f,F,(,v,i,v,j,)=,b,ij,;,当,f,ij,=,C,ij,时,v,j,v,i,E,f,F,(,v,j,v,i,)=,-,b,ij,;,当,0,f,ij,C,ij,时,v,i,v,j,E,f,F,(,v,i,v,j,)=,b,ij,v,j,v,i,E,f,F,(,v,j,v,i,)=,-,b,ij,.,然后,转向,.,53,求出含有负权的有向赋权图,G,f,=,(,V,E,f,F,),中发点,v,s,到收点,v,t,的最短路,若最,短路,存在转向,;,否则,f,是所求的最小费用最大流,停止,.,增流,.,v,i,v,j,与,相同,v,i,v,j,与,相反,.,令,=min,ij,|,v,i,v,j,重新定义流,f,=,f,ij,为,其它情况不变,.,如果,W,f,大于或等于预定的流量值,则适当减少,值,使,W,f,等于预定的流量值,那么,f,是,所求的最小费用流,停止,;,否则转向,.,54,下面介绍求解有向赋权图,G,=(,V,E,F,),中含有负权的最短路的,Ford,算法,.,设边的权,v,i,v,j,为,w,ij,v,1,到,v,i,的路长记为,(,i,).Ford,算法的迭代步骤,(P160-161),：,赋初值,(1)=0,(,i,)=,i,=2,3,n,.,更新,(,i,),i,=2,3,n,.,(,i,)=min,(,i,),min,(,j,),+,w,ji,|,j,i,.,若所有的,(,i,),都无变化,停止,;,否则转向,.,在算法的每一步,(,i,),都是从,v,1,到,v,i,的最短路长度的上界,.,若不存在负长回路,则从,v,1,到,v,i,的最短路长度是,(,i,),的下界,经过,n,-,1,次迭代后,(,i,),将保持不变,.,若在第,n,次迭代后,(,i,),仍在变化时,说明存在负长回路,.,55,6.5,关键路径问题,一项工程任务,大到建造一座大坝,一座体育中心,小至组装一台机床,一架电视机,都要包括许多工序,.,这些工序相互约束,只有在某些工序完成之后,一个工序才能开始,.,即它们之间存在完成的先后次序关系,一般认为这些关系是预知的,而且也能够预计完成每个工序所需要的时间,.,这时工程领导人员迫切希望了解最少需要多少时间才能够完成整个工程项目,影响工程进度的要害工序是哪几个？,56,PT(Potentialtask graph),图,在,PT(Potentialtask graph),图中,用结点表示工序,如果工序,i,完成之后工序,j,才能启动,则图中有一条有向边,(,i,j,),其长度,w,i,表示工序,i,所需的时间,.,这种图必定不存在有向回路,否则某些工序将在自身完成之后才能开始,这显然不符合实际情况,.,在,PT,图中增加两个虚拟结点,v,0,和,v,n,使所有仅为始点的结点都直接与,v,0,联结,v,0,为新增边的始点,这些新增边的权都设为,0;,使所有仅为终点的结点都直接与,v,n,联结,v,n,为新增边的终点,.,这样得到的图,G,仍然不存在有向回路,.,57,例 一项工程由,13,道工序组成,所需时间,(,单位：天,),及先行工序如下表所示,(P172).,工序序号,A B C D E F G H I,所需时间,2 6 3 2 4 3 8 4 2,先行工序,A A B C,D D D D G,H,工序序号,J K L M,所需时间,3 8 5 6,先行工序,G H,E J K,试问这项工程至少需要多少天才能完成,?,那些工程不能延误,?,那些工程可以延误,?,最多可延误多少天,?,58,先作出该工程的,PT,图,.,由于除了工序,A,外，均有先行工序,因此不必虚设虚拟结点,v,0,.,A,B,2,2,C,6,D,3,E,2,F,2,G,2,H,2,K,4,N,3,I,8,J,8,4,4,2,L,3,M,8,5,6,在,PT,图中,容易看出各工序先后完成的顺序及时间,.,虚拟结点,59,A,B,2,2,C,6,D,3,E,2,F,2,G,2,H,2,K,4,N,3,I,8,J,8,4,4,2,L,3,M,8,5,6,这项工程至少需要多少天才能完成,?,就是要求,A,到,N,的最长路,此路径称为,关键路径,.,那些工程不能延误,?,那些工程可以延误,?,最多可延误多少天,?,关键路径上的那些工程不能延误,.,60,关键路径,(,最长路径,),算法,定理,若有向图,G,中,不存在有向回路,则可以将,G,的结点重新编号为,u,1,u,2,u,n,使得对任意的边,u,i,u,j,E,(,G,),都有,i,j,.,各工序最早启动时间算法步骤：,根据定理,对结点重新编号为,u,1,u,2,u,n,.,赋初值,(,u,1,),=0,.,依次更新,(,u,j,),j,=2,3,n,.,(,u,j,),=max,(,u,i,)+,(,u,i,u,j,)|,u,i,u,j,E,(,G,).,结束,.,其中,(,u,j,),表示工序,u,j,最早启动时间,而,(,u,n,),即,(,v,n,),是整个工程完工所需的最短时间,.,61,A,B,2,2,C,6,D,3,E,2,F,2,G,2,H,2,K,4,N,3,I,8,J,8,4,4,2,L,3,M,8,5,6,此例不必重新编号，只要按字母顺序即可,.,(A)=0,(B)=,(C)=2,(D)=8,(E)=,max,2+3,8+2=10,(F)=,(G)=,(H)=,(D)+2=10,(I)=,max,(G)+8,(H)+4=18,(J)=,(G)+8=18,(K)=,max,(E)+4,(H)+4=14,(L)=,(J)+3=21,(M)=,(K)+8=22,(N)=,max,(F)+3,(I)+2,(L)+5,(M)+6=28.,关键路径,?,62,通过以上计算表明：,这项工程至少需要,28,天才能完成,.,关键路径,(,最长路径,):,ABDEKMN,ABDHKMN,工序,A,B,D,E,H,K,M,不能延误,否则将影响工程的完成,.,但是对于不在关键路径上的工序,是否允许延误？如果允许,最多能够延误多长时间呢？,各工序允许延误时间,t,(,u,j,),等于各工序最晚启动时间,(,u,j,),减去各工序最早启动时间,(,u,j,).,即,t,(,u,j,)=,(,u,j,)-,(,u,j,).,63,最晚启动时间算法步骤,(,已知结点重新编号,),：,赋初值,(,u,n,)=,(,u,n,).,更新,(,u,j,),j,=,n,-,1,n,-,2,1,.,(,u,j,),=min,(,u,i,)-,(,u,i,u,j,)|,u,i,u,j,E,(,G,).,结束,.,顺便提一句,根据工序,u,j,允许延误时间,t,(,u,j,),是否为,0,可判断该工序是否在关键路径上,.,64,A,B,2,2,C,6,D,3,E,2,F,2,G,2,H,2,K,4,N,3,I,8,J,8,4,4,2,L,3,M,8,5,6,(N)=28,(M)=28-6=22,(L)=28-5=23,(K)=,(M)-8=14,(J)=,(L)-3=20,(I)=28-2=26,(H)=,min,(K)-4,(I)-4=10,(G)=,min,(J)-8,(I)-8=12,(F)=,28,-3=25,(E)=,(K)-4=10,(D)=,min,(E)-2,(F)-2,(G)-2,(H)-2=8,(C)=,(E)-3=7,(B)=,(D)-6=2,(A)=0.,65,各工序允许延误时间如下：,t,(A)=,t,(B)=,t,(D)=,t,(E)=,t,(H)=,t,(K)=,t,(M)=0,t,(C)=5,t,(F)=15,t,(G)=2,t,(I)=8,t,(J)=2,t,(L)=2.,66,PERT,图,在,PERT(Programme evaluation and review technique),图中,采用有向边表示工序,其权值表示该工序所需时间,.,如果工序,e,i,完成后,e,j,才能开始,则令,v,k,是,e,i,的终点,e,j,的始点,.,根据这种约定,前,例的,PERT,图如下：,A,B,C,E,F,D,D,G,G,H,H,I,J,K,L,M,对于,PERT,图,一些算法与,PT,图,类似,.,67,PT,图要比,PERT,图好一些,.,PT,图的结点数基本上是固定的,这是最重要的一点,容易编程计算,.,另外,PT,图,比,PERT,图更加灵活,它能适应一些额外的约束,.,例如下图中,(,i,),/,2,v,i,v,j,(,i,)+,t,v,i,v,j,b,j,v,0,v,j,表示工序,v,i,完成一半之后,v,j,就可以开始,.,表示工序,v,i,完成后经过,t,时刻,v,j,才开始,.,表示在时间,b,j,之后工序,v,j,才能开始,其中,v,0,表示虚拟结点,.,68,6.6,网络最优化模型转化为线性规划模型,本节将某些网络最优化问题转化为线性规划问题来求解,但这并不意味着线性规划的方法是解决这些网络最优化问题的最有效算法,.,事实上,这些网络最优化问题均各自存在更有效的算法,.,我们之所以将它们转化为线性规划问题,主要基于以下两个方面的考虑：,我们有现成的功能很强的软件,它可以方便地求解线性规划问题,.,将某些网络最优化模型,转化为线性规划模型,本身就是一种非常好的建模训练,具体的转化技巧具有重要的启发意义,.,69,6.7,系统监控模型,定义,1,设图,G,=(,V,E,),K,V,如果图,G,的每条边都至少有一个顶点在,K,中,则称,K,是,G,的一个,点覆盖,.,若,G,的一个点覆盖中任意去掉一个点后不再是点覆盖,则称此点覆盖是,G,的一个,极小点覆盖,.,顶点