网络流最大流算法.ppt

Network Flow Presented by Network Flow 基本性质： 对于网络(G,u,s,t) 1、容量限制(Capacity Constraints):F(x,y) = C(x,y) 2、流量守恒(Flow Conservation):ΣF(v,x) = ΣF(x,u) 3、斜对称性(Skew Symmetry): F(x,y) = -F(y,x) 讨论的前提： G为简单有向图 网络(G,u,s,t)中所有容量均为整数 最大流(max-flow)问题，就是求在满足网络流性质的情况下，源点 s 到汇点 t 的最大流量。 Ford–Fulkerson algorithm Definition： 1、剩余图(residual graph)： 2、剩余容量(residual capacity)： Ford–Fulkerson algorithm Definition： 3、一条f可扩路(the augmenting path)：剩余图中的一条s-t路 4、给定一个流f及剩余图中的一条路(或圈)P，沿P使f扩充r：对每一个e∈E(P) 若e∈E(G)，则令f(e)增加r； 设e0∈E(G)，若e为e0的反向边，则令f(e0)减小r 注：此处的路径P不一定是可扩路 Ford–Fulkerson algorithm 输入：网络（G、u、s、t）及各边容量 输出：一条最大值的s-t流f 算法描述： 1、初始时令所有边的流量f=0； 2、求出剩余图(residual graph) ，并在 中找一条可扩路(the augmenting path)P。若无可扩路，则终止； 3、算出P路中各边剩余容量的最小值r，并沿P使f扩充r，转2； Maximum Flow-Minimum Cut Theorem Definition： 1、s-t流：指满足如下条件的流： a、源点流出量0 b、除s、t点外，图G中的所有点流量守恒 注：此处的s-t流不单指图中特定的s-t路 s-t流的值：源点s的流出量； 2、s-t割：即点集S指向点集T（此处T=V(G)\X）的边集，其中s∈S且t∈T 割的容量：各边容量之和 最小s-t割：在G中关于u具有最小容量的s-t割 Maximum Flow-Minimum Cut Theorem Definition： Maximum Flow-Minimum Cut Theorem 任一个网络(G,u,s,t)中，最大流的流量等于最小割的容量 证明： 1、任意一个流小于等于任意一个割(S,T)，即value(F) = cap(S,T) 2、s∈S，t∈T当且仅当(S,T)中每条边的f都饱和，而(T,S)中每条边的f都为零时上式取等 3、设F为网络的最大流，K为最小割， 则value(F) = cap(K) s∈S，t∈T；其中，令S = {v∈V(G)|从源s到v有f可扩路}∪{s}； 则t?S（否则存在s-t可扩路，可得到更大的流），从而K = (S,T)是网络中的一个割，故cap(K) = cap(K); 又可证(S,T)中每条边的f都饱和，而(T,S)中每条边的f都为零，故value(F) = cap(K) = cap(K) 综上，value(F) = cap(K) Theorem 网络N(G,u,s,t)中的可行流f是N的最大流当且仅当N中不存在f可扩路 必要性：若有可扩路P，沿P使f扩大即可 充分性：设网络中不存在可扩路 令S = {v∈V(G)|从源s到v有f可扩路}∪{s}，则与最大流最小割定理同样可证K = (S,T)是网络中的一个割，且value(f) = cap(K) 设F为最大流，K为最小割，则value(f) = value(F) = cap(K) = cap(K) 故f即为最大流，K即为最小割 Ford–Fulkerson算法的劣势： Edmonds–Karp algorithm -最大流问题的第一个多项式时间算法 与Ford–Fulkerson算法相比，改进之处在于第二步中P路径的选择，与其任选，不如选最短（边数最少） 算法步骤： 1、令所有边的流量f=0； 2、在 中找条最短可扩路P，若无，则止； 3、算出P路中各边剩余容量的最小值r，并沿P使f扩充r，转2； 复杂度： Edmonds–Karp可在O(m*m*n)内得解 Edmonds–Karp算法中无论边容量多大，最多增流m*n/2次（m为边数，n为点数） 每次增流用BFS最大为O(m) Dinics algorithm Definition： 分层图(level graph) 首先，分层图是基于剩余图的 其次，分层图会对所有顶点标号（与s的距离） 最后，分层图