《算法艺术与信息学竞赛》第八讲最大流问题.ppt

《算法艺术与信息学竞赛》教学幻灯片 算法图论 第八讲 最大流问题 声明 本系列教学幻灯片属于刘汝佳、黄亮著《算法艺术与信息学竞赛》配套幻灯片 本幻灯片可从本书blog上免费下载，即使您并未购买本书. 若作为教学使用，欢迎和作者联系以取得技术支持，也欢迎提供有不同针对性的修改版本，方便更多人使用 有任何意见，欢迎在blog上评论 Blog地址： 内容介绍 一、最大流问题 二、Ford-Fulkerson方法 三、Edmond-Karp算法 四、预流推进算法 五、应用举例 一、最大流问题 流网络定义 一个流网络(flow network) G=(V,E)是一个有向图, 每个边(u,v)有一个非负容量(capacity) c(u,v)=0. 对于不在E中的(u, v), 规定c(u, v)=0 有两个特殊结点: 源(source) s和汇(sink) t. 假设对于任意其他点v, 存在通路s?v?t 流的定义 流(flow)是一个边的函数f(u,v), 满足: 容量限制: f(u,v)=c(u,v) 对称性: f(u,v)=-f(u,v) 收支平衡: 对于不是s或t的其他点u, 有 把整个网络的流量定义为(即从s流出的流量): 最大流问题: 寻找流函数f, 使得网络流最大 记号 X和Y为结点集, 定义记号f(X, Y) 引理: 在以f为流函数的流网络中, 以下三个等式成立 f(X, X) = 0 F(X, Y) = -f(X, Y) 若X和Y不相交, f(XUY, Z) = f(X,Z)+f(Y,Z) 可以定义流的加法和标量积(注意容量限制) 可以证明: 可行流集合是凸的, 即如果f1和f2都是流, 对于所有0=α=1, αf1+(1-α)f2也是. 其他问题 弧的两个方向同时有流量? 可以进行流取消(cancelling)只保留一边 附加s和t, 则s-t流变为循环流 流分解定理: 任意循环流可以分解为不超过E个有向环的并 二、Ford-Fulkerson方法 基本思想 从零流开始迭代, 每次沿着增广路(augmenting path)调整流量,直到不存在增广路, 算法停止 算法梗概 残量网络 有的弧已经满载了, 不可能增加流量, 在寻找可增广路时应该避免. 引入残量网络(residual network), 表示所有可以增加流量的弧 定义(u,v)的残量容量为: cf(u,v)=c(u,v)-f(u,v) 注意: 流量为负时, 残量容量比原始容量还大! 可以这样理解: 在取消反向流量以后还可以增加正向流量, 因此流量增加量(而不是终值)可以大于原始容量 残量网络举例 残量网络: 大于0的cf所构成的网络 由于一条弧最多从两边增广, |Ef|=2|E| 可增广路 残量网络中任意一条s-t路称为可增广路 路上的最小容量称为路的残量容量(residual capacity), 记为d 对于可增广路上的有向边(u,v), 原始网络的流量f(u,v)增加d, 由对称性，f(v,u)减少d, 则得到的新流也是可行流(验证流的三个性质) 定理: 流量f是最大流当且仅当残量网络中不存在可增广路 最小切割最大流定理 网络G=(V,E)的s-t切割(cut)是把V划分成S和T=V-S, 使得s在S中, t在T中 使用前面介绍的隐式求和记号, 可以简单的定义切割(S,T)的净流量(net flow)为f(S,T), 容量(capacity)为c(S,T) 下图的割, 流量为19(注意有反向流), 容量为26 切割与流 最小切割(minimum cut)是使c(S,T)最小的切割 定理: 对于任意一个切割, f(S,T)=|f|. 证明: f(S,T)=f(S,V)-f(S,S)=f(S,V)=f(s,V)+f(S-s,V)=f(s,V) (最后一步的根据是流量平衡) 推论: |f|不会超过任意一个切割的容量, 因此任意流量不会超过最小切割的容量 定理: 最大流等于最小切割的容量 最小切割最大流定理 定理: 以下三个条件等价 f是最大流 残量网络中无可增广路 存在某个切割(S,T), |f|=c(S,T) 证明 1?2: 反证. 若存在, 可沿它增广得到更大流 2?3: 此时不存在s-t通路. 定义S为s可达结点集, T为可达t结点集, 则|f|=c(S,T) (若跨越(S,T)的弧不满载, 残量网络中会有更多弧存在) 3?1: 根据刚才的推论可证 基本的Ford-Fulkerson算法 不断迭代. 每次寻找某一条可增广路. 若(u,v)和(v,u)都不在图中出现, 则c(u,v)=f(u,v)=0. 注意: 允许c(u,v)和c(v,u)都大于0 时间复杂度 对于整数容量, 可以用DFS/BFS求残量网络的任意一条s-t路, 最多增广|f*|