第四章网络流问题.ppt
《第四章网络流问题.ppt》由会员分享,可在线阅读,更多相关《第四章网络流问题.ppt(38页珍藏版)》请在得力文库 - 分享文档赚钱的网站上搜索。
1、第四章 网络流问题4.1 网络及网络流定义1:称N=(V,E,c,X,Y)为一个网络,如果:(1)G=(V,E)是一个有向图;(2)c是E上的非负函数,称为容量函数,对每条边e,c(e)称为边e的容量;(3)X与Y是V的两个非空不相交子集,分别称为G的发点集与收点集,I=V/(XY)称为G的中间点集.X的顶点称为发点或源,Y的顶点称为收点或汇,I的顶点称为中间点.若|X|1,|Y|1,称N为多源多汇网络;若|X|=1,|Y|=1,则称N为单源单汇网络.定义2:设N是一个网络,f是E上的非负函数,如果:(1)0f(e)c(e),eE;(2),vI 其中:N+(v)表示v的所有出弧的集,N-(v)
2、表示v的所有入弧的集.则称f是网络N的一个流,f(e)是e的流量.注:条件(1)称为容量约束,表示通过边的流量不能超过该边的容量;条件(2)称为守恒条件,表示在每个中间点,流进与流出该顶点的总流量相等,即保持中间点的流量平衡.例1:下图表示一个网络及网络流,其中发点集:X=x1,x2,收点集:Y=y1,y2,y3,中间点集:I=v1,v2,v3,v4,每条边上的前一个数字表示容量,后一个数字表示流量.x1x2y1y2y3v1v2v3v41,16,15,12,23,24,44,42,23,05,31,01,04,03,12,16,0注:设AV,引入记号:则守恒条件可写为:f+(v)=f-(v),
3、vI.显然,任一网络至少存在一个流,如零流(f(e)=0,eE)定义3:设f是网络N的一个流,AV,则称f+(A)-f-(A)为流出A的净流量,称f-(A)-f+(A)为流入A的净流量.注:流入,流出任何中间点的净流量为0引理:设f是网络N的一个流,则:f+(X)-f-(X)=f-(Y)-f+(Y)即流出发点集X的净流量等于流入收点集Y的净流量.定义4:设f是网络N的一个流,则f的流的价值valf定义为:valf=f+(X)-f-(X),即流的价值是发点集的流出量,也是收点集的流入量.例如:例1中的网络N的流的价值为:Valf=f(x1,v1)+f(x1,v4)+f(x2,v3)+f(x2,v
4、4)=f(v1,y1)+f(v2,y1)+f(v2,y3)+f(v3,y3)=6 任何一个网络N=(V,E,c,X,Y),都等价于单源单汇网络,记为:N=(V,E,c,s,t)(1)V=Vs,t,s与t分别是N的发点与收点;(2)E=E|xX|yY;(3)c(e)=c(e),eE;c=,xX;c=,yY 在解决实际问题时,常把多源多汇网络转化为单源单汇网络,如例1的转化为:对于单源单汇网络N=(V,E,c,s,t),有:Valf=f+(s)=f-(t)所以上图中:valf=6x1x2y1y2y3v1v2v3v41,16,15,12,23,24,44,42,23,05,31,01,04,03,1
5、2,16,0,2,4,0,6,04.2 最大流问题4.2.1 定义定义1:设N=(V,E,c,s,t)是一个网络,f是一个流,若不存在流f,使得:valfvalf,则称f为N的最大流.定义2:若AV,sA,tAc=V-A,则记:(A,Ac)=N+(A)称为网络N的一个割,而:cap(A,Ac)=称为割(A,Ac)的容量.设K是一个割,若不存在割K,使得:capKcapK,则称K为N的最小割.注:割是从A到Ac的有向弧组成的.4.2.2 最大流与最小割的关系定理1:设f是网络N的流,(A,Ac)是一个割,则:(1)valf=f+(A)-f-(A)(2)valfcap(A,Ac).定理2:设f是流
6、,K是割,若valf=capK,则f是最大流,是K最小割,定理3:网络N的最大流的价值等于最小割的容量.注:定理2与定理3合并为:f是流,K是割,valf=capK的充分必要条件是f是最大流,K是最小割.4.2.3 增广链及最大流算法定义3:若f为网络N上的一个流,对eE:(1)若f(e)=c(e),则称e为f的饱和弧;(2)若f(e)0,则称e为f的正弧;(4)若f(e)=0,则称e为f的零弧.定义4:若P是网络N中的从发点s到收点t的一条初等链(点,边不重复的路),定义链的方向为从s到t,则链上的弧(有向边)分为两类:一类是弧的方向与链的方向一致,叫做正向弧;另一类弧与链的方向相反,叫做反
7、向弧.正向弧的全体记为P+,反向弧的全体记为P-.定义5:设l(P)=,其中:若l(P)=0,则称链P为f-饱和链;若l(P)0,则称链P为f-非饱和链.定义6:设f是一个流,P是s到t的一条链,若P满足下列条件:(1)在弧eP+上,0f(e)c(e),即P+中每一条弧都是非饱和弧;(2)在弧eP-上,0f(e)c(e),即P-中每一条弧都是非零弧.则称P为关于流f的一条增广链.注:显然,一条f-增广链就是一条从发点s到收点t的f-非饱和链.在网络中存在一条f-增广链,表明f不是最大流.事实上,沿着P附加上流l(P),便得到一个新的流f,其定义如下:对于这个流,有valf=valf+l(P),
8、称为基于P的改进流.定理4:f是网络N的最大流的充分必要条件是N不含f-增广链.最大流算法的基本思想:判别网络N中当前给定的流f(初始时,取f为零流)是否存在增广链,若没有,则该流f为最大流;否则,求出f的改进流f,把f看成f,再进行判断和计算,直到找到最大流为止.算法(标号法):网络N=(V,E,c,s,t)1.对任意的e=E,置f=0;标发点为(s+,),令s=;2.若点x已标号,则对与x相邻的未标号的点y,按下法标号:a.E,当fc时,令:y=minc-f,x给y标(x+,y);当f=c时,不给y标号;b.E,当f0时,令:y=minf,x给y标(x-,y);当f=0时,不给y标号;3.
9、重复2直至收点t被标号或不存在可标号的点.若t被标号,则转4;若t不能被标号且不存在可以标号的点,则停止,输出fv;4.令u=t;5.若u的标号为(v+,u),则令:f=f+t,若u的标号为(v-,u),则令:f=f-t;6.若v=s,则去掉除发点s的所有点的标号,转2;否则令u=v,转5.算法的第2-3步为标号过程,第4-6步为增流过程.标号(x+,y)表示从x流入y的流可增加y,(x-,y)表示从y流入x的流可减少y,(s+,)表示发点可提供任意多的流量到别的点.算法终止后,令已标号的点的集为S,则割(S,Sc)即为最小割,从而最大流的流量valf=cap(S,Sc)例:求下图中网络N=(
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 第四章 网络流问题 第四 网络 问题
限制150内