运筹学最大流问题.ppt

4最大流,定义 有向连通图G=(V,E),G的每条边(vi,v j)称作弧上有,c i j 称为边的容量,仅有一个入次为0的点v i 称为,中间点,这样的网络G称为容量网络,常记为 G=(V,E,C).,对任一G中的边(vi,v j)有流量 f i j,称为集合 f=f i j 为,网络G上的一个流。称满足下列条件的流 f 为可行流：,(1)容量限制条件:对G中每条边(vi,vj),有0fij cij;,(即中间点v i 的输入量与输出量相等).,(即从v s 点发出总量等于v t与输入总量相等).,一、最大流有关概念,非负权,发点(源),一个入次为0的点vi 称为收点(汇),其余的点称为,定义,容量网络G=(V,E,C),vi,v j 收、发点,若有 边集E,为E的子集,将G分为两个子图G1,G2,其顶点集合分别记S,E为E的真子集,而 G(V,E-E)仍连通,G(V,E-E)不连通;,一个流f=f i j,f i j=c i j,则称流 f 对边(vi,vj)是饱和的.,列出图示网络全部割,边上数字为 c i j(f i j).,V,s,v1,v2,v3,v4,t,s,v1,v2,v4,s,v1,v2,v3,s,v2,v4,s,v1,v3,s,v1,v2,s,v2,s,v1,s,v1,v2,v3,v4,t,v2,v3,v4,t,v1,v3,v4,t,v3,v4,t,v2,v4,t,v1,v3,t,v4,t,v3,t,(s,1),(s,2),(s,2),(1,2),(s,1),(1,3),(s,1),(2,4),(s,2),(4,t),(1,3),(2,4),(4,3),(1,2),(3,2),(3,t),(2,4),(3,t),(4,3),(4,t),(1,3),(3,t),15,(4,t),21,17,18,19,24,14,25,15,割,容量,4-3、最大流-最小割定理,定理,定理2(最大流-最小割定理)任一网络G中,从vs 到 vt 的,定义,设 f 为网络G=(V,E,C)的任一可行流,流量为W,容量网络G,若为网络中从 vs 到 vt 的一条链,给,定向为从 vs 到 vt,上的边凡与同向称为前向边,凡,与反向的称为后向边，其集合分别用+和-表示,f 是,一个可行流,如果满足,则称为从 v s 到 v t 的(关于 f)的可增广链.,最大流的流量等于分离 vs,vt 的最小割的容量.,推论 可行流f是最大流的充要条件是不存在从vs 到 vt 的(关于f 的)可增广链.,4-4、求最大流的标号算法,若vt得到标号,说明存在一条可增广链,转(第2步)调整过程.,给发点vs以标号(0,+).,选择一个已标号的顶点 vi,对于vi,的所有未给标号的邻,(a)若边(vj,vi)E,且 f j i 0,则令j=min(f j i,j),并给 v j 以标号(-v i,j).,1.标号过程,(b)若边(vi,vj)E,且 f i j c i j 时,令j=min(c i j-f i j,i),并给 v j 以标号(+v i,j).,重复直到收点 vt 被标号或不再有顶点可标号为止.,若vt未得到标号,标号过程已无法继续,说明 f 已是最大流.,接点 vj,按下列规则处理:,2.调整过程,令 fi j=,去掉所有标号,回到第1步,对可行流 f 重新标号.,f i j+t 若(vi,v j)是可增广链上的前向边,f i j-t 若(vi,v j)是可增广链上的后向边,f i j 若(vi,v j)不在可增广链上,作 业,阅读 p258-265,p43 15,17,图,边集(vs,v1),(v1,v3),(v2,v3),(v3,vt),(v4,vt),都是割集.,9,11,割集容量,边集(vs,v1),(vs,v3),(vs,v4),例14_A,图中一个网络及初始可行流,边上序数为(c i j,f i j),先给 vs 标号(,+).,检查 vs 的邻接点v1,v2,v3,边(vs,v2)E,且 f s 2 c s 2=4,同理 给 v3 以标号+vs,1.,检查v2尚未标号邻接点v5,v6,边(v2,v6)E,且 f25=0 c 25=3,检查v5尚未标号邻接点v1,vt,边(v1,v5)E,且 f15=30,给 v2 以标号+vs,2.,v4尚未标号与v1邻接,给 v4 以标号+v1,2.,类似给 vt 以标号+v4,2.,因 vt 得以标号，,(v1,v4)E且 f14=2c14=5,给 v5 以标号+v2,2.,给 v1 以标号-v5,2.,说明存在增广链,标号过程结束.,求此网络的最大流。,1.标号过程,例14_B,边上序数为(c i j,f i j),2.调整过程,由 v4的标号找到点v1,沿逆可增广链向据标号找到 v4,由 v1的标号找到点v5,由 v5的标号找到点v2,由 v2的标号找到点v s,已逆至源 vs,调整结束。,重新标号过程,由 vs只能去v3,但v3下游饱和,vt不可能获得标号,5+4+2=fs1+fs2+fs3=f4t+f5t+f5t=4+3+4=11=W,算法结束。,例14_C,边上序数为(c i j,f i j),标号点集合为S,即 S=vs,v3,用标号法在得到最大流的同时,与最大流的流量相等。,割集容量,可得到一个最小割.见图中虚线.,C(S,S)=cs1+cs2+c36=11,最小割意义:网络由发点到收点,的各通路中,由容量决定其通过能力,最小割是这些路中的咽喉部分,其容量最小,它决定了整个网络的最大通过能力。,四、最大匹配问题,|M|表示集合M中M的边数。,一个图的最大匹配中所含边数是确定的,但匹配方案可以不同。,定义23 二部图G=(X,Y,E),M是边集E的子集,若M中的任意,若不存在另一匹配M1,使得|M1|M|,则称M为最大匹配.,二部图中最大匹配问题可以化为最大流问题。,在二部图中增加发点和收点,用有向边与原二部图中顶点,两条边都没有公共端点,则称M为图G的一个匹配(对集),相连,令全部边上的容量均为1.当此网络的流达到最大时,即获最大匹配方案.,例15,有5位待业者，5项工作，他们各自胜任工作情况,如图，要求设计一个方案，使量多的人能就业。,