• / 98
  • 下载费用:10 金币  

最大流问题.ppt

关 键 词:
最大流问题.ppt
资源描述:
9-5 最大流问题 一、几个概念 定义(前向弧和后向弧)在任意一顶点之处,凡离开vi的有向弧称为vi的前向弧,凡进入vi的有向弧称为vi的后向弧。,,vi,vj,a,称有向弧a为vi点的前向弧, vj点的后向弧。,,,定义(道路或通路)在任意一网络中,凡从始点v0(发点)开始到终点vn(收点)结束的一系列前向弧集合称为道路。记为P。,,,,,,,,,,,v0,vn,v2,v1,,,,,,,,,,,v0,vn,v2,v1,V0——V1——Vn,,,,,,,,,,,v0,vn,v2,v1,,,,,,,,,,,v0,vn,v2,v1,V0——V1——Vn,,,,,,,,,,,v0,vn,v2,v1,V0——Vn,,,,,,,,,,,v0,vn,v2,v1,,,,,,,,,,,v0,vn,v2,v1,,,,,,,,,,,v0,vn,v2,v1,V0——V1——V2——Vn,,,,,,,,,,,v0,vn,v2,v1,,,,,,,,,,,v0,vn,v2,v1,V0——V2——Vn,,,,,,,,,,,v0,vn,v2,v1,,,,,,,,,,,v0,vn,v2,v1,,,,,,,,,,,v0,vn,v2,v1,V0——V2——V1——Vn,定义:(截集或割集) 如果N表示某网络中所有点的集合,将N分成两个子集S与S,使得发点v0在S内,收点vn在S 内,则称(S,S)为分离发点与收点的截集。显然,SS=N ,SS=,V0 S ,VnS,,,,,,,,,,,v0,vn,v2,v1,,a,,截集a:v0v1,v0v2,v0vn,,,,,,,,,,,v0,vn,v2,v1,,b,,截集b:v1vn,v2vn,v0vn,,,,,,,,,,,v0,vn,v2,v1,,c,截集c:v1vn,v1v2,v2v1,v0v2 ,v0vn,,,,,,,,,,,v0,vn,v2,v1,,d,截集d:v0v1,v1v2,v2v1,v2vn,v0vn,定义(截集的容量)从S中各顶点到S中各顶点全部容量之和称为截集的容量(截量),用(S,S)表示。,截集a: Ca=C01+C02+C0n 截集b: Cb=C1n+C2n+C0n 截集c: Cc=C1n+C12+ C02+ C0n 截集d: Cd=C01+C21+ C2n+ C0n,,,,,,,,,,,v0,vn,v2,v1,,c,S,S,在截集c中边v2v1是反向的,其容量视为零。,,,,,,,,,,,,v0,vn,v2,v1,,d,S,S,在截集d中边v1v2是反向的,其容量视为零。,,定义(最小截量) 一个网络中,各种截集中容量最小的称为最小截量,用min C(S,S)表示。,现在我们把一个网络看成是一个自来水管网络,煤气管网络,电力线网络或公路网络,铁路网络,水运交通网络等,都可以归纳成一个运输问题,称为网络流,值得关心问题是在这样一个网络中最大流为多少?,定义(流)若对网络N,函数f满足如下条件: (1)0  fij  Cij (i,j)E(N) (2)f-(vi) = f+(vi) iV(N) 则称f为N的一个网络流,简称流。,定义(最大流)若 f 为N的一个网络流,而N中不存在流 f ,使得 f f ,则称 f 为一个最大流,记Max f 。,截量 C与流 f 的关系任一有向网络流,如果 f 是从发点到收点的流量,C(S,S)是任一个截集,则 f  C(S,S) 。等号什么时候成立?,定理(最小截量 最大流)任一有向网络流,从发点到收点的最大流量Max f 等于最小截量Min C(S,S) 。即: Max f = Min C(S,S),最大流算法 设P=v0v1v2….vn为网络中的一条通路,记E(P)=(所有P中的前向弧和后向弧) 令(P)=min (i,j) 其中 (i,j)= Cij-fij (vi,vj)是前向弧fij (vi,vj)是后向弧,,其中Cij是边容量, f(i,j) 是流过边 vivj 的可行流,( f(i,j)  Cij) 定义:若 (P)=0 称P为f 的饱和的;若 (P)0 称P为f 的不饱和的。 定义:一条从发点到收点的 f不饱和通路称为f 的增长道路(增流路)。,在一个网络中,f 的增长道路的存在表示 f 不是最大流。所以。沿着P增加一个值为 (P)的附加流,得到一个新流:f(i,j)+ (P) (vi,vj)是前向弧 f(i,j)= f(i,j)- (P) (vi,vj)是后向弧f(i,j) 其他,,新流f(i,j)的流值为 :f= f + (P) 称f为基于P的修改流; 显然 f f 定理:当且仅当N中不包含 f 增长道路时,N中的流 f 是最大流。,算法的基
展开阅读全文
  微传网所有资源均是用户自行上传分享,仅供网友学习交流,未经上传用户书面授权,请勿作他用。
0条评论

还可以输入200字符

暂无评论,赶快抢占沙发吧。

关于本文
本文标题:最大流问题.ppt
链接地址:https://www.weizhuannet.com/p-9861311.html
微传网是一个办公文档、学习资料下载的在线文档分享平台!

微传网博客

网站资源均来自网络,如有侵权,请联系客服删除!

 网站客服QQ:80879498  会员QQ群:727456886

copyright@ 2018-2028 微传网络工作室版权所有

     经营许可证编号:冀ICP备18006529号-1 ,公安局备案号:13028102000124

收起
展开