学年计算机方向课程大二下算分15网络流

D

AAB工厂A: 工厂B:商店C: 商店D: AB: AC:BC: BD:CD:？---24边集EeE,容量ce0一个s-tfER+f(e)ef满足容量条件:eE0f(e守恒条件:除源点汇点外的结点v，f(e) fe进入f的流量等于从源点出发的所有边的流量之和求：具有最大流量的s-t流

f(e)f(e)从源点到汇点的一条简单路径P={e1,e2,…,ek}，其中ei为前向边或后向边且f(ei)>0，i=1,2,…,k，称P为增广路径，所f(P)=min{f(ei)|uu tvs–u–vt，增加流ustvustv解f(su)= f(uv)=u tvf(sv)=10,u tvf(ut)=最大流的值f，剩余图Gf=(Vf,Ef)，其中Vf=V，Ef由可以增加流的若e=(u,v)，且f(e)<ceeEfc’ece若e=(u,v)，且f(e)>0e’=(v,u)Efc’eusftusftvustvGusust解v6u f’tvAugment(f,Pf,增广路径bbottleneck(Pf)//P所增加流量—fori1toifeithenelse return时间

fori1tomwhileGPaa5sbctdaasbctdaasbctdaasbctdaasbctd解aasbctdv(f)命题 算法Augment(f,P)的输出仍旧是一个流证设输入流为ff.增加的流量为P上的eiP，0f(ei)ce若为前向边，增广后0f(ei)ce，若为后向边，增广后流量减少但不少于0.满足0f(ei)ce.对P上任意内结点v，f在v满足守恒条件.P进入v的边为ei,ei+1eiei+1都是前向边，eiv的流增加,ei+1流出的也增加，流量守恒.若ei为前向边，ei+1为后向边，ei进入v的流增加，ei+1流入v的减少，流量守恒.其他两种情况同理可证.每次增广操作流值将增加 增广路径P的第一条边是从s出发的前向边，P是简单路径，不会再经过s，因此v(f)=v(f)+bottleneck(P,f由于bottleneck(Pf)>0v(fv(f假设容量都是整数，令C是从sC cee(s,u那么至多C次增广操作后，算法将终止时间复杂度Gf2mGfO(m时间Gfs-t的简单路径，用深度优先或宽度优n-1O(n时间CO(mC.s-t

设有向图G=(V,E)，一个s-t割是V的一个划分(A,B)，使得sAtB，A,BV，割(A,B)的容量记为c(A,B)A出来c(A,B) e从Au tu tv 令f是任意s-t流,(A,B)是任意s-t割，那v(f) v(f)=fout(s)fin(s)=fvf)uA{s}，fout(u)=fvf)v(f)u

out(u)ffout(A)ffout(A)

定理2f是使得在剩余图Gfs-t路径的一个s-t流,那么在G中存在一个s-t割(A,B)使得v(f)=c(A,于是，f是G中最大流，(A,B是G中最小s-t割证：Av|vPPGfs 显然sA,tB,(A,B)是s-t Gfs-t注：蓝色边为剩余图Gf中的边 e和e’不是剩余图Gf的边e=(u,v),uA,vBf(e)<ce，则e于是vA，矛盾 e’=(u’,v’),u’B,v’Af(e’)=0f(e’)>0，则e’在剩余图中，于是u’A，矛盾.v(f)fout(s)fout(s)fout(A)fin(

0c(A,在每