网络流最大流算法

Network FlowPresented by Network Flow基本性质：基本性质：对于网络对于网络(G,u,s,t)1、容量限制、容量限制(Capacity Constraints):F(x,y)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 TheoremDefinition：Maximum Flow-Minimum Cut Theorem 任一个网络任一个网络(G,u,s,t)中，最大流的流量等于最小中，最大流的流量等于最小割的容量割的容量证明：证明：1、任意一个流小于等于任意一个割、任意一个流小于等于任意一个割(S,T)，即，即value(F)=cap(S,T)2、sS，tT当且仅当当且仅当(S,T)中每条边的中每条边的f都饱和，而都饱和，而(T,S)中每条边中每条边的的f都为零时上式取等都为零时上式取等3、设、设F为网络的最大流，为网络的最大流，K为最小割，为最小割，则则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算法的算法的ExampleFujishige algorithm 传说中的传说中的弱多项式弱多项式算法算法 对简单有向图对简单有向图G以及整容量可在以及整容量可在O(mn )时时间内正确求解最大流问题，其中间内正确求解最大流问题，其中n为点数、为点数、m为边数、为边数、u max为最大边容量（详见课本为最大边容量（详见课本153）maxu logFujishige algorithmFujishige algorithm 简单粗暴的说：简单粗暴的说：1、每一次迭代都从、每一次迭代都从s出发（出发（s即即v1），按当前的），按当前的最大量（最大量（）往）往t流流a、只能往前流（、只能往前流（v1v2v3.），若到达），若到达t点，转点，转2b、若途经某边剩余容量、若途经某边剩余容量流出的点流出的点（即超出量（即超出量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)+1Pushrelabel算法可在算法可在O()时间内解决问题时间内解决问题（详见课本（详见课本157）mn2GomoryHu algorithm 未完待续 to be continued