第四章 网络流问题

《第四章 网络流问题》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

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/(X∪Y)称为G的中间点集.X的顶点称为发点或源,Y的顶点称为收点或汇,I的顶点称为中间点.若

2、X

3、>1,

4、Y

5、>1,称N为多源多汇网络;若

6、X

7、=1,

8、Y

9、=1,则称N为单源单汇网络.定义2:设N是一个网络,f是E上的非负函数,如果:(1)0≤f(e)≤c(e),e∈E;(2

10、),v∈I其中:N+(v)表示v的所有出弧的集,N-(v)表示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,

11、42,23,05,31,01,04,03,12,16,0注:设AV,引入记号:则守恒条件可写为:f+(v)=f-(v),v∈I.显然,任一网络至少存在一个流,如零流(f(e)=0,e∈E)定义3:设f是网络N的一个流,AV,则称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+

12、(X)-f-(X),即流的价值是发点集的流出量,也是收点集的流入量.例如:例1中的网络N的流的价值为:Valf=f(x1,v1)+f(x1,v4)+f(x2,v3)+f(x2,v4)=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=V∪{s,t},s与t分别是N的发点与收点;(2)E=E∪{

13、x∈X}∪{

14、y∈Y};(3)c(e)=c(e),e∈E;c=∞,x∈X;c

15、=∞,y∈Y在解决实际问题时,常把多源多汇网络转化为单源单汇网络,如例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,12,16,0∞,2∞,4∞,0∞,6∞,04.2最大流问题4.2.1定义定义1:设N=(V,E,c,s,t)是一个网络,f是一个流,若不存在流f,使得:valf>valf,则称f为N的最大流.定义2:若AV,s∈A,t∈Ac=V

16、-A,则记:(A,Ac)=N+(A)称为网络N的一个割,而:cap(A,Ac)=称为割(A,Ac)的容量.设K是一个割,若不存在割K,使得:capK

17、pK的充分必要条件是f是最大流,K是最小割.4.2.3增广链及最大流算法定义3:若f为网络N上的一个流,对e∈E:(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,则链上的弧(有向边)分为两类:一类是弧的方向与链的方向一致,叫做正向弧;另一类弧与链的方向相反,叫做反向弧.正向弧的全体记为P+,反向弧的全体记为P-.定义5:

18、设l(P)=,其中:若l(P)=0,则称链P为f-饱和链;若l(P)>0,则称链P为f-非饱和链.定义6:设f是一个流,P是s到t的一条链,若P满足下