文档介绍：Network Flow
Presented by
Network Flow
基本性质:
对于网络(G,u,s,t)
1、容量限制(Capacity Constraints):F(x,y) <= C(x,y)
2、流量守恒(Flow Conservation):ΣF(v,x) = ΣF(x,u)
3、斜对称性(Skew Symmetry): F(x,y) = -F(y,x)
讨论的前提:
G为简单有向图
网络(G,u,s,t)中所有容量均为整数
最大流(max-flow)问题,就是求在满足网络流性质的情况下,源点 s 到汇点 t 的最大流量。
Ford–Fulkerson algorithm
Definition:
1、剩余图(residual graph):
2、剩余容量(residual capacity):
Ford–Fulkerson algorithm
Definition:
3、一条f可扩路(the augmenting path):剩余图中的一条s-t路
4、给定一个流f及剩余图中的一条路(或圈)P,沿P使f扩充r:对每一个e∈E(P)
若e∈E(G),则令f(e)增加r;
设e0∈E(G),若e为e0的反向边,则令f(e0)减小r
注:此处的路径P不一定是可扩路
Ford–Fulkerson algorithm
输入:网络(G、u、s、t)及各边容量
输出:一条最大值的s-t流f
算法描述:
1、初始时令所有边的流量f=0;
2、求出剩余图(residual graph) ,并在中找一条可扩路(the augmenting path)P。若无可扩路,则终止;
3、算出P路中各边剩余容量的最小值r,并沿P使f扩充r,转2;
Maximum Flow-Minimum Cut Theorem
Definition:
1、s-t流:指满足如下条件的流:
a、源点流出量>0
b、除s、t点外,图G中的所有点流量守恒
注:此处的s-t流不单指图中特定的s-t路
s-t流的值:源点s的流出量;
2、s-t割:即点集S指向点集T(此处T=V(G)\X)的边集,其中s∈S且t∈T
割的容量:各边容量之和
最小s-t割:在G中关于u具有最小容量的s-t割
Maximum Flow-Minimum Cut Theorem
Definition:
Maximum Flow-Minimum Cut Theorem
任一个网络(G,u,s,t)中,最大流的流量等于最小割的容量
证明:
1、任意一个流小于等于任意一个割(S,T),即value(F) <= cap(S,T)
2、s∈S,t∈T当且仅当(S,T)中每条边的f都饱和,而(T,S)中每条边的f都为零时上式取等
3、设F为网络的最大流,K为最小割,
则value(F) <= cap(K)
s∈S,t∈T;其中,令S = {v∈V(G)|从源s到v有f可扩路}∪{s};
则t∉S(否则存在s-t可扩路,可得到更大的流),从而K' = (S,T)是网络中的一个割,故cap(K') >= cap(K);
又可证(S,T)中每条边的f都饱和,而(T,S)中每条边的f都为零,故value(F) = cap(K') >= cap(K)
综上,value(F) = cap(K)