《运筹学_最大流问题》由会员分享，可在线阅读，更多相关《运筹学_最大流问题（13页珍藏版）》请在金锄头文库上搜索。
1、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与输入总量相等).,一、最大流有关概念,非负权,发点(源),一个入
2、次为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,
3、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 为
4、网络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, +).,选择一个已标号的
5、顶点 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 =,去掉所有标号, 回
6、到第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
7、标号(, +).,检查 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.,说明存在增广链, 标号过程结束.,求此网络的
8、最大流。,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,用标号法在得到最大流的同时,与最大流的流量相等。,割集容量,可
9、得到一个最小割. 见图中虚线.,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项工作，他们各自胜任工作情况,如图，要求设计一个方案，使量多的人能就业。,
