最大网络流

时间:2017-07-29 14:32:21   收藏:0   阅读:405

     问题定义     

流网络

 G中流

最大流问题

给定一个流网络G、一个源结点s、一个汇点t,找到值最大的一个流

定义:出发点为源点,接受流量 的汇聚点为汇点,边上的权值为可以流过的最大值

     几个关键定义     

残存网络Gf:由仍可以对流量进行增加/减少的边构成(流过的量不超过容量的边),包含原图中的边,以及可能包含对应的反向边

残存容量cf:一条边还可以增加的最大流量(与容量c不同,c表示的是一开始就确定的流量最大值)

技术分享

由cf再定义一次Gf:cf>0的边

为什么要在Gf中加反向边?

通过增加反向边,让我们可以撤销原来的流量操作。为什么要撤销呢?

来自《数据结构与算法分析》上的一个例子

原图 流图(原图上的流) 残余网络  
技术分享 技术分享 技术分享

残余网络中没有增加反向边

s->t没有新的可达路径

算法结束,但没有达到目的

(得到最大流)

 原来的网络流图

0/5表示边的容量为5

图中每条边上流量的一个状态

选择一条可达路径s-a-d-t

发送流量=3到这条路径上 

技术分享

增加了反向边,

s->t存在新的可达路径

原来s-a-d-t的流撤销一部分

被撤销的部分可以分流到其它路径

增广路径:给定流网络G=(V, E),增广路径是残存网络中一条从源结点到汇点的简单路径(没有分支)

流网络的切割

流网络G=(V, E)的一个切割就是将结点集合划分成两个集合S和T(T=V-S)

技术分享

设f为流网络G=(V, E)中的一个流,该流网络的源结点为s,汇点为t,则下面的条件等价

     Ford-Fulkerson方法     

基本步骤

  1. 寻找一条增广路径p,用p来对流进行修改(增加)
  2. 直到没有任何增广路径

整理了一下概念,接下来找找例子再补一下

 

参考

1. 《算法导论》原书第3版

2. 《数据算法与算法分析——C语言描述》原书第2版

原文:http://www.cnblogs.com/coolqiyu/p/7251643.html

评论(0
© 2014 bubuko.com 版权所有 - 联系我们:wmxa8@hotmail.com
打开技术之扣,分享程序人生!