文档介绍：workFlow基本性质:对于网络(G,u,s,t)1、容量限制(CapacityConstraints):F(x,y)<=C(x,y)2、流量守恒(FlowConservation):ΣF(v,x)=ΣF(x,u)3、斜对称性(SkewSymmetry):F(x,y)=-F(y,x)讨论的前提:G为简单有向图网络(G,u,s,t)中所有容量均为整数最大流(max-flow)问题,就是求在满足网络流性质的情况下,源点s到汇点t的最大流量。Ford–FulkersonalgorithmDefinition:1、剩余图(residualgraph):2、剩余容量(residualcapacity):Ford–FulkersonalgorithmDefinition:3、一条f可扩路(theaugmentingpath):剩余图中的一条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–Fulkersonalgorithm输入:网络(G、u、s、t)及各边容量输出:一条最大值的s-t流f算法描述:1、初始时令所有边的流量f=0;2、求出剩余图(residualgraph),并在中找一条可扩路(theaugmentingpath)P。若无可扩路,则终止;3、算出P路中各边剩余容量的最小值r,并沿P使f扩充r,转2;MaximumFlow-MinimumCutTheoremDefinition:1、s-t流:指满足如下条件的流:a、源点流出量>0b、除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割MaximumFlow-MinimumCutTheoremDefinition:MaximumFlow-MinimumCutTheorem任一个网络(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)