资源描述：
《【5A版】网络流最大流算法.ppt》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、NetworkFlowPresentedbyNetworkFlow基本性质：对于网络(G,u,s,t)1、容量限制(CapacityConstraints):F(x,y)<=C(x,y)2、流量守恒(FlowConservation):ΣF(v,x)=ΣF(x,u)3、斜对称性(SkewSymmetry):F(x,y)=-F(y,x)讨论的前提：G为简单有向图网络(G,u,s,t)中所有容量均为整数最大流(max-flow)问题，就是求在满足网络流性质的情况下，源点s到汇点t的最大流量。Ford–FulkersonalgorithmDefinition
2、：1、剩余图(residualgraph)：2、剩余容量(residualcapacity)：Ford–FulkersonalgorithmDefinition：3、一条f可扩路(theaugmentingpath)：剩余图中的一条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–Fulkersonalgorithm输入：网络（G、u、s、t）及各边容量输出：一条最大值的s-t流f
3、算法描述：1、初始时令所有边的流量f=0；2、求出剩余图(residualgraph)，并在中找一条可扩路(theaugmentingpath)P。若无可扩路，则终止；3、算出P路中各边剩余容量的最小值r，并沿P使f扩充r，转2；MaximumFlow-MinimumCutTheoremDefinition：1、s-t流：指满足如下条件的流：a、源点流出量>0b、除s、t点外，图G中的所有点流量守恒注：此处的s-t流不单指图中特定的s-t路s-t流的值：源点s的流出量；2、s-t割：即点集S指向点集T（此处T=V(G)X）的边集，其中s∈S且t∈T割
4、的容量：各边容量之和最小s-t割：在G中关于u具有最小容量的s-t割MaximumFlow-MinimumCutTheoremDefinition：MaximumFlow-MinimumCutTheorem任一个网络(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(
5、G)
6、从源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)
7、从源s到v有f可扩路}∪{s}，则与最大流最小割定理同样可证K'=(
8、S,T)是网络中的一个割，且value(f)=cap(K')设F为最大流，K为最小割，则value(f)<=value(F)<=cap(K)<=cap(K')故f即为最大流，K'即为最小割Ford–Fulkerson算法的劣势：Edmonds–Karpalgorithm-最大流问题的第一个多项式时间算法与Ford–Fulkerson算法相比，改进之处在于第二步中P路径的选择，与其任选，不如选最短（边数最少）算法步骤：1、令所有边的流量f=0；2、在中找条最短可扩路P，若无，则止；3、算出P路中各边剩余容量的最小值r，并沿P使f扩充r，转2；复杂度：Ed
9、monds–Karp可在O(m*m*n)内得解Edmonds–Karp算法中无论边容量多大，最多增流m*n/2次（m为边数，n为点数）每次增流用BFS最大为O(m)Dinic'salgorithmDefinition：分层图(levelgraph)首先，分层图是基于剩余图的其次，分层图会对所有顶点标号（与s的距离）最后，分层图中只存在这样的剩余边(u,v)：dist(v)=dist(u)+1，不符合这一规律的边全部删去Dinic'salgorithmDefinition：阻塞流(blockingflow)：网络(G,u,s,t)对应的分层图中所有可扩路
10、的并，即为阻塞流Dinic'salgorithm算法步骤：1、令所有边的流量f=0；2、构造剩
