网络流最大流算法.ppt

上传人:小飞机 文档编号:5301280 上传时间:2023-06-23 格式:PPT 页数:28 大小:1.60MB
返回 下载 相关 举报
网络流最大流算法.ppt_第1页
第1页 / 共28页
网络流最大流算法.ppt_第2页
第2页 / 共28页
网络流最大流算法.ppt_第3页
第3页 / 共28页
网络流最大流算法.ppt_第4页
第4页 / 共28页
网络流最大流算法.ppt_第5页
第5页 / 共28页
点击查看更多>>
资源描述

《网络流最大流算法.ppt》由会员分享,可在线阅读,更多相关《网络流最大流算法.ppt(28页珍藏版)》请在三一办公上搜索。

1、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、剩余图(re

2、sidual 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、求出

3、剩余图(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割,Maximu

4、m 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

5、=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扩充

6、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)对应的分层图中所有可扩路的并,即为阻

7、塞流,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

8、 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):

9、流入-流出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,

展开阅读全文
相关资源
猜你喜欢
相关搜索

当前位置:首页 > 生活休闲 > 在线阅读


备案号:宁ICP备20000045号-2

经营许可证:宁B2-20210002

宁公网安备 64010402000987号