《中科院算法课程第6-3节-图算法-最大流》由会员分享，可在线阅读，更多相关《中科院算法课程第6-3节-图算法-最大流（13页珍藏版）》请在金锄头文库上搜索。
1、2019/5/24,1,电子与通信工程学院 ,第6.3节 最大流 Network flow,1,6.3.1 问题的定义 6.3.2 流网络 6.3.3 Ford-Fulkeson算法 6.3.4 最大二步匹配问题,提纲,2019/5/24,2,最大流问题,有向图G=(V, E), 容量c : ER+, 源点s, 汇点t, 求容量限制下, 能从s运送到t的最大量 若在边(u,v)上运送单位物质费用为h(u,v), 则有最小费用最大流问题,能否观察出最大流的上界?,流, 流量, 最大流,称 f: VVR 为流, 若f 满足： (1) 容量限制, f(u,v) c(u,v) (2) 反对称性, f(
2、u,v) = -f(v,u) (3) 流守恒性, 任意uVs, t, vV f(u,v) = 0 流量 |f| = vV f(s,v). 最大流: 给定流网络G, s, t, c, 求 max |f| : f是G的流,流网络, 残余网络,假设任意vV, 存在有从svt的路径 容量c: VVR+, (u, v)E: c(u, v) 0; (u, v)E: c(u, v) = 0. 流网络：有向图G=(V,E), s, t, c. 流f的残余流量, cf(u,v) = c(u,v) - f(u,v). 残余网络, Gf=(V, Ef), Ef = (u,v) | cf(u,v)0 ,增广路径,增广
3、路径: Gf中从s到t的一条简单路径 增广路径的残余容量: 若p为增广路径, 则称 cf(p) = min cf(u,v) : (u,v)p 为p的残余容量, 是Gf中能沿p传输的最大量.,两个性质,引理1. 给定G=(V, E), s, t, c, f, Gf . 设p为一条增 广路径, 定义 fp(u,v) = cf(p), 若(u,v)p = -cf(p), (v,u)p = 0, else 则fp是Gf上的流, |fp| = cf(p). 推论1 给定G=(V,E), s, t, c, f, Gf . p是Gf上的增广路径, 则f+fp是流，并且此流是单调增加的： |f+fp| |f|
4、 .,流网络的割,割(S,T): (1) T=V-S (2) sS, tT. f(S,T)=uS,vTf(u,v) : f是穿过割(S, T)的净流 c(S,T)=uS,vT c(u,v) : 割是(S,T)的容量 例.下图中的割(S, T), S=s,v1,v2,T=v3,v4,t. f(S,T)=19, c(S,T)=26.,流值,引理2：设f是源点为s，汇点为t的流网络G中的一个流, 并且(S, T)是G的一个割。则通过割(S, T)的流值是网络流值|f|,最大流最小割定理,推论2. 对于流网络G中的任意流f来说，其值的上界为G的人任意割的容量:,最大流最小割定理. 如果f是给定G=(V
5、, E), s, t 中的一个流，则下列条件是等价的: 1) f是G的一个最大流 2) 残留网络Gf不包含增广路径 3) 对于G的某个割(S, T)，有|f| = c(S,T),Ford-Fulkerson 算法,FORD-FULKERSON G(s, t) For all (u, v) belongs to E(G) do fu, v 0 do fv, u 0 while there is a residual path p do cpu,v mincu,v: (u,v) is on p for (u,v) on p do fu, v fu, v+ cpu,v; fv, u -fu, v; return f,Ford-Fulkerson 算法复杂度分析,Ford-Fulkerson, 容量为整数, O(|E| |f*|) |f*|表示流的最大单位，则4-8的while循环至多执行 |f*|次，而每个循环中寻找增广路径的复杂度为O(|E|),谢 谢,2019/5/24,13,
