梳理与总结:大流量/小割值算法详解
1。基本定理:最小割集的流量之和=网络中的最大流。
这个定理说明,当网络达到最大流时,会有一个割集,这个割集中的所有边都达到饱和状态。
这等价于在网络中再也找不到一个从s到t的增广路径。
因为只要能找到一条增广路径,这条增广路径肯定要经过最小割集中的一条边,否则这个割集就不能称之为割集了。
既然这个割集中所有的边都饱和了,因此也就不会存在这样的增广路径了。
这个定理的意义在于给我们指明了方向:
任何算法,只要最后能达到“再也找不到一条增广路径”,就可以说明这个算法最后达到了最大流。
2。
解决最大流问题的常用到Ford-Fulkerson方法,之所以称其方法而不是算法,是因为在这种思想下包含着若干种时间复杂度不同的实现,其中较多地是使用Edmonds-Karp算法。与此相对,Push-relabel算法采用了与Ford-Fulkerson方法完全不同的思考角度,降低了渐进意义下的时间复杂度。而relabel-to-front算法则是对Push-relabel算法的改良和精炼,效率更佳。
关于这三种常用算法的时间复杂度可见下表:(其中V表示图的顶点数,E表示边数)
算法名称
|
Edmonds-Karp算法
|
一般性的push-relabel算法
|
relabel-to-front算法
|
时间复杂度
|
O(V*E^2)
|
O(V^2*E)
|
O(V^3)
|
可以看出,当给定的有向图比较稀疏时,三种算法的效率不会相差太多,但当网络稠密时,relabel-to-front算法在效率上有着明显的优势。
这几种算法可以参见《算法导论》里有详细的证明。
第一种思路(Ford-Fulkerson)是不断地找一条增广路径,然后算出这个增广路径里的最小允许通过的流,然后在source上加入这个流量。
也就是说不断小心翼翼地加入流量,使之最终饱和。
第二种思路(push-relable)是先加入充足的流(跟s相连的所有边的容量之和),加入之后呢,再慢慢一个边一个边的向汇点渗透。直到没法再渗透(找不到增广路径了),那么这时再把一些剩余的流回收到source就可。
3。求最大流和求最小割集是两类不同的算法。
4。求解最小割集普遍采用Stoer-Wagner算法
上一篇: 快乐计算(BZOJ 2127): 少量切割找到满足群体划分的幸福方案
下一篇: poj 2914: 斯托尔-王纳算法求解 最小切割问题 (Minimum Cut using Stoer-Wangner Algorithm)
推荐阅读