logo

您所在位置网站首页 > 海量文档  > 计算机 > 软件编程

图论算法最大流算法.ppt 39页

本文档一共被下载: ,您可全文免费在线阅读后下载本文档。

  • 支付并下载
  • 收藏该文档
  • 百度一下本文档
  • 修改文档简介
全屏预览

下载提示

1.本站不保证该用户上传的文档完整性,不预览、不比对内容而直接下载产生的反悔问题本站不予受理。
2.该文档所得收入(下载+内容+预览三)归上传者、原创者。
3.登录后可充值,立即自动返金币,充值渠道很便利
特别说明: 下载前务必先预览,自己验证一下是不是你要下载的文档。
  • 上传作者 爱是你我(上传创作收益人)
  • 发布时间:2019-05-15
  • 需要金币100(10金币=人民币1元)
  • 浏览人气
  • 下载次数
  • 收藏次数
  • 文件大小:568.5 KB
下载过该文档的会员
你可能关注的文档:
图论算法 ---最大流问题 运输网络 现在想将一些物资从S运抵T,必须经过一些中转站。连接中转站的是公路,每条公路都有最大运载量。 每条弧代表一条公路,弧上的数表示该公路的最大运载量。最多能将多少货物从S运抵T? 4 2 4 8 4 7 3 6 2 1 S T V1 V2 V3 V4 公路运输图 基本概念 这是一个典型的网络流模型。为了解答此题,我们先了解网络流的有关定义和概念。 若有向图G=(V,E)满足下列条件: 有且仅有一个顶点S,它的入度为零,即d-(S) = 0,这个顶点S便称为源点,或称为发点。 有且仅有一个顶点T,它的出度为零,即d+(T) = 0,这个顶点T便称为汇点,或称为收点。 每一条弧都有非负数,叫做该边的容量。边(vi, vj)的容量用cij表示。 则称之为网络流图,记为G = (V, E, C) 可行流 可行流 对于网络流图G,每一条弧(i,j)都给定一个非负数fij,这一组数满足下列三条件时称为这网络的可行流,用f表示它。 1. 每一条弧(i,j)有fij≤Cij 2. 流量平衡 除源点S和汇点T以外的所有的点vi,恒有: ∑j(fij)= ∑k(fjk) 该等式说明中间点vi的流量守恒,输入与输出量相等。 3. 对于源点S和汇点T有 , ∑i(fSi)= ∑j(fjT)= V(f) 可改进路 给定一个可行流f={fij}。若fij = Cij,称<vi, vj>为饱和弧;否则称<vi, vj>为非饱和弧。若fij = 0,称<vi, vj>为零流弧;否则称<vi, vj>为非零流弧。 定义一条道路P,起点是S、终点是T。把P上所有与P方向一致的弧定义为正向弧,正向弧的全体记为P+;把P上所有与P方向相悖的弧定义为反向弧,反向弧的全体记为P-。 譬如在图中,P = (S, V1, V2, V3, V4, T),那么 P+ = {<S, V1>, <V1, V2>, <V2, V3>, <V4, T>} P- = {<V4, V3>} 给定一个可行流f,P是从S到T的一条道路,如果满足: fij是非饱和流,并且<i,j>∈ P+ , fij是非零流,并且<i,j>∈ P- 那么就称P是f的一条可改进路。(有些书上又称:可增广轨)之所以称作“可改进”,是因为可改进路上弧的流量通过一定的规则修改,可以令整个流量放大。 割切 G = (V, E, C)是已知的网络流图,设U是V的一个子集,W = V\U,满足SU,TW。即U、W把V分成两个不相交的集合,且源点和汇点分属不同的集合。 对于弧尾在U,弧头在W的弧所构成的集合称之为割切,用(U,W)表示。把割切(U,W)中所有弧的容量之和叫做此割切的容量,记为C(U,W),即: 上例中,令U = {S, V1},则W = {V2, V3, V4, T},那么 C(U, W) = <S, V2> + <V1, V2> + <V1, V3>+<V1, V4> =8+4+4+1=17 割切 上例中,令U = {S, V1},则W = {V2, V3, V4, T},那么, C(U, W) = <S, V2> + <V1, V2> + <V1, V3>+<V1, V4> =8+4+4+1=17 流量算法的基本理论 定理1:对于已知的网络流图,设任意一可行流为f,任意一割切为(U, W),必有:V(f) ≤ C(U, W)。 定理2:可行流f是最大流的充分必要条件是:f中不存在可改进路。 定理3:整流定理。 如果网络中所有的弧的容量是整数,则存在整数值的最大流。 定理4:最大流最小割定理。 最大流等于最小割,即max V(f) = min C(U, W)。 最大流算法 第1步,令x=(xij)是任意整数可行流,可能是零流,给s一个永久标号(-, ∞)。 第2步(找增广轨),如果所有标号都已经被检查,转到第4步。 找到一个标号但未检查的点i, 并做如下检查, 对每一个弧(i,j),如果xij<Cij, 且j未标号,则给j一个标号(+i, δ(j) ),其中, δ(j)=min{Cij-xij , δ(i) } 对每一个弧(j, i),如果xji>0,且j未标号,则给j一个标号(-i, δ(j) ),其中, δ(j)=min{xji , δ(i) } 第三步(增广),由点t开始,使用指示标号构造一个增广路,指示标号的正负则表示通过增加还是减少弧流量来增加还是减少弧流量来增大流量,抹去s点以外的所有标号,转第二步继续找增广轨。 第四步(构造最小割),这时现行流是最大的,若把所有标号的集合记为S,所有未标号点的集合记为T,便得到最小容量割(S,T)。 实例 复杂度分析 设图中弧数为m,每找一条增广轨最多需

发表评论

请自觉遵守互联网相关的政策法规,严禁发布色情、暴力、反动的言论。
用户名: 验证码: 点击我更换图片

2010-2013 max.book118.com在线文档投稿赚钱网. All Rights Reserved 蜀ICP备08101938号