网络流最大流算法.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 的最大流量。,FordFulkerson algorithm,Definition：1、剩余图(residual graph)：2、剩余容量(residual capacity)：,FordFulkerson algorithm,Definition：3、一条f可扩路(the augmenting path)：剩余图中的一条s-t路4、给定一个流f及剩余图中的一条路(或圈)P，沿P使f扩充r：对每一个eE(P)若eE(G)，则令f(e)增加r；设e0E(G)，若e为e0的反向边，则令f(e0)减小r注：此处的路径P不一定是可扩路,FordFulkerson 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、源点流出量0b、除s、t点外，图G中的所有点流量守恒注：此处的s-t流不单指图中特定的s-t路s-t流的值：源点s的流出量；2、s-t割：即点集S指向点集T（此处T=V(G)X）的边集，其中sS且tT割的容量：各边容量之和最小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(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=vV(G)|从源s到v有f可扩路s，则与最大流最小割定理同样可证K=(S,T)是网络中的一个割，且value(f)=cap(K)设F为最大流，K为最小割，则value(f)=value(F)=cap(K)=cap(K)故f即为最大流，K即为最小割,FordFulkerson算法的劣势：,EdmondsKarp algorithm-最大流问题的第一个多项式时间算法,与FordFulkerson算法相比，改进之处在于第二步中P路径的选择，与其任选，不如选最短（边数最少）算法步骤：1、令所有边的流量f=0；2、在 中找条最短可扩路P，若无，则止；3、算出P路中各边剩余容量的最小值r，并沿P使f扩充r，转2；复杂度：EdmondsKarp可在O(m*m*n)内得解EdmondsKarp算法中无论边容量多大，最多增流m*n/2次（m为边数，n为点数）每次增流用BFS最大为O(m),Dinics algorithm,Definition：分层图(level graph)首先，分层图是基于剩余图的其次，分层图会对所有顶点标号（与s的距离）最后，分层图中只存在这样的剩余边(u,v)：dist(v)=dist(u)+1，不符合这一规律的边全部删去,Dinics algorithm,Definition：阻塞流(blocking flow)：网络(G,u,s,t)对应的分层图中所有可扩路的并，即为阻塞流,Dinics algorithm,算法步骤：1、令所有边的流量f=0；2、构造剩余图的分层图(level graph)3、在分层图中求一个阻塞的s-t流(the blocking flow)f，若f=0，则止4、用f对f扩充，转2复杂度：在一定基础上可达O(mn log n)，其中，n为点数、m为边数（详见课本153）,Dinic算法的Example,Dinic算法的Example,Fujishige algorithm,传说中的弱多项式算法对简单有向图G以及整容量可在O(mn)时间内正确求解最大流问题，其中n为点数、m为边数、u max为最大边容量（详见课本153）,Fujishige algorithm,Fujishige algorithm,简单粗暴的说：1、每一次迭代都从s出发（s即v1），按当前的最大量（）往t流a、只能往前流（v1v2v3.），若到达t点，转2b、若途经某边剩余容量，则缩减（缩小一半向下取整），然后重新迭代（在对应剩余图的基础上除了啥也没变）。注：若=0，则终止2、从s出发的流成功到达t（假设为v6）沿途经过的顶点按顺序为：s(v1)-v2-v3.t(v6)沿途经的边使流量f扩充，得到新的剩余图，转1,Pushrelabel maximum flow algorithm（推流-重标算法）,Definition：1、超出量(Flow Excess)：流入-流出2、活动点(active)：除s、t外，流入流出的点（即超出量0的点）,Pushrelabel maximum flow algorithm（推流-重标算法）,Definition：3、距离标号(distance labels,or heights):a、h(s)=n,h(t)=0；（s和t的标号是固定的）b、剩余图中的所有边(u,v)，有h(u)=h(v)+1；4、容许(admissible)边：剩余图中的边(u,v)，且h(u)=h(v)+1；,Pushrelabel maximum flow algorithm（推流-重标算法）,算法步骤：1、令s的出边满流，其余边f=0（也可不置零）2、画出剩余图，令s的高度(height)h(s)=n，其余点h(v)=03、若有活动点，执行：设v为活动点：v点有容许边e，则push(e)v点无容许边，则relabel(v)Push(e)在v点的超出量e(v)与e的剩余容量中选出较小者r沿e使f扩充rRelabel(v)在剩余图的(v,w)中找出高度最小的点w令h(v)=h(w)+1,Pushrelabel算法可在O()时间内解决问题（详见课本157）,GomoryHu algorithm,未完待续to be continued,
