资源描述：
《网络流算法介绍与分析》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
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)(
