网络流算法介绍与分析

网络流算法介绍与分析

ID:43755418

大小:356.00 KB

页数:89页

时间:2019-10-13

网络流算法介绍与分析_第1页
网络流算法介绍与分析_第2页
网络流算法介绍与分析_第3页
网络流算法介绍与分析_第4页
网络流算法介绍与分析_第5页
资源描述:

《网络流算法介绍与分析》由会员上传分享,免费在线阅读,更多相关内容在行业资料-天天文库

1、网络流杭州学军中学魏越闽一些符号和定义V表示整个图中的所有结点的集合.E表示整个图中所有边的集合.G=(V,E),表示整个图.s表示网络的源点,t表示网络的汇点.对于每条边(u,v),有一个容量c(u,v)(c(u,v)>=0)如果c(u,v)=0,则表示(u,v)不存在在网络中。如果原网络中不存在边(u,v),则令c(u,v)=0对于每条边(u,v),有一个流量f(u,v).v1tsv2(2,2)(4,4)(2,4)(0,3)(2,2)一个简单的例子.网络可以被想象成一些输水的管道.括号内右边的数字表示管道的容量,左边的数字表示这条管道的当前流量.网

2、络流的三个性质1、容量限制:f[u,v]<=c[u,v]2、反对称性:f[u,v]=-f[v,u]3、流量平衡:对于不是源点也不是汇点的任意结点,流入该结点的流量和等于流出该结点的流量和。结合反对称性,流量平衡也可以写成:只要满足这三个性质,就是一个合法的网络流.最大流问题定义一个网络的流量(记为

3、f

4、)=最大流问题,就是求在满足网络流性质的情况下,

5、f

6、的最大值。残量网络为了更方便算法的实现,一般根据原网络定义一个残量网络。其中r(u,v)为残量网络的容量。r(u,v)=c(u,v)–f(u,v)通俗地讲:就是对于某一条边(也称弧),还能再有多少流量

7、经过。Gf残量网络,Ef表示残量网络的边集.例1v1tsv2(2,2)(4,4)(2,4)(0,3)(2,2)v1tsv2232422原网络(a,b)表示(流量f,容量c)残量网络(如果网络中一条边的容量为0,则认为这条边不在残量网络中。r(s,v1)=0,所以就不画出来了。另外举个例子:r(v1,s)=c(v1,s)–f(v1,s)=0–(-f(s,v1))=f(s,v1)=4.图1图2例1从残量网络中可以清楚地看到:因为存在边(s,v2)=3,我们知道从S到v2还可以再增加2单位的流量;因为存在边(v1,t)=2,我们知道从v1到t还可以再增加2单

8、位的流量。v1tsv2232422后向弧其中像(v1,s)这样的边称为后向弧,它表示从v1到s还可以增加4单位的流量。但是从v1到s不是和原网络中的弧的方向相反吗?显然“从v1到s还可以增加4单位流量”这条信息毫无意义。那么,有必要建立这些后向弧吗?v1tsv2232422为什么要建立后向弧显然,例1中的画出来的不是一个最大流。但是,如果我们把s->v2->v1->t这条路径经过的弧的流量都增加2,就得到了该网络的最大流。注意到这条路径经过了一条后向弧:(v2,v1)。如果不设立后向弧,算法就不能发现这条路径。从本质上说,后向弧为算法纠正自己所犯的错误

9、提供了可能性,它允许算法取消先前的错误的行为(让2单位的流从v1流到v2)为什么要建立后向弧当然,可以把上面说的情况当成特殊情况来处理。但使用后向弧可以使编程简单许多.注意,后向弧只是概念上的,在程序中后向弧与前向弧并无区别.增广路增广路定义:在残量网络中的一条从s通往t的路径,其中任意一条弧(u,v),都有r[u,v]>0。绿色的即为一条增广路。v1tsv2232422增广路算法增广路算法:每次用BFS找一条最短的增广路径,然后沿着这条路径修改流量值(实际修改的是残量网络的边权)。当没有增广路时,算法停止,此时的流就是最大流。下面证明增广路算法的正确

10、性.将f,c,r的定义域扩展为点集(在以后的叙述中,大写字母X,Y,S,T一般均表示点集)点集间的流量和:f(X,Y)=即:X中的任意一点与Y中的任意一点组成的所有边上的流量之和.(边的方向为从X中的结点到Y中的结点)c,r等函数都有类似的定义.(点集间的容量和、点集间的残量网络容量和)结论11.f(X,X)=0(由流量反对称性)2.f(X,Y)=-f(Y,X)(有流量反对称性)3.f(X∪Y,Z)=f(X,Z)+f(Y,Z)(显然)4.f(X,Y∪Z)=f(X,Y)+f(X,Z)(显然)最大流最小割定理网络流中这三个条件等价(在同一个时刻):1、f是

11、最大流2、残量网络中找不到增广路径3、

12、f

13、=c(S,T)1、f是最大流2、残量网络中找不到增广路径3、

14、f

15、=c(S,T)1->2证明:显然.假设有增广路径,由于增广路径的容量至少为1,所以用这个增广路径增广过后的流的流量肯定要比f的大,这与f是最大流矛盾.割的定义一个割(S,T)由两个点集S,T组成.S+T=Vs属于S.t属于T.提出割的定义,是为后面的证明作铺垫.结论2(点集总流量为零)不包含s和t的点集,于它相关联的边上的流量之和为0.证明:f(X,V)==(由流量平衡)=0结论3任意割的流量等于整个网络的流量.证明:f(S,T)=f(S,V)

16、–f(S,S)(由辅助定理1)=f(S,V)(由辅助定理1)=f(S,V)+f(S–s,V)(

当前文档最多预览五页,下载文档查看全文

此文档下载收益归作者所有

当前文档最多预览五页,下载文档查看全文
温馨提示:
1. 部分包含数学公式或PPT动画的文件,查看预览时可能会显示错乱或异常,文件下载后无此问题,请放心下载。
2. 本文档由用户上传,版权归属用户,天天文库负责整理代发布。如果您对本文档版权有争议请及时联系客服。
3. 下载前请仔细阅读文档内容,确认文档内容符合您的需求后进行下载,若出现内容与标题不符可向本站投诉处理。
4. 下载文档时可能由于网络波动等原因无法下载或下载错误,付费完成后未能成功下载的用户请联系客服处理。