发布时间 : 星期三 文章网络流模型总结更新完毕开始阅读
59146965 福州一中 肖汉骏
2. Ford-Fulkerson方法
1) 退流概念
1/3 1/5 C 2/2 1/3 S 1/1 A 0/3 B 0/4 D 图4.1
T
求解过程中的困惑：
[问题1]流量还可能增加吗？
0/2 E [问题2]如果能增加，怎样改进？ 退流的概念——后向弧
仔细分析图4.1，我们发现，流量是可以增加的：
S 1/3 1/1 B A 0/5 1/3 C 1/2 T 1/3 1/4 D 图4.2 1/2 E 把一个流量弧(B,C)和(C,T)上的流退回到B点，改道从B-D-E-T走，就可以增加流量了，如下图：
2/3 A S 1/1 B 2/3 1/5 C 2/2 T 1/3 1/4 D 图4.3 1/2 E 图4.1不能“直接寻找增大流的路径”，是因为当初有些弧上的流选择不“恰当”，要“退流”。 一种直观的想法就是：调整或重新搜索“当初的选择”——难！
能不能保留以前的工作，而在这之上改进呢？经过专家们研究发现，加入退流思想——后向弧，就能再次“直接寻找增大流的路径”。
第 5 页 共 15 页
59146965 福州一中 肖汉骏
2) 增广路径(可改进路径)的定义
若P是网络中连结源点s和汇点t的一条路，我们定义路的方向是从s到t，则路上的弧有两种：
前向弧——弧的方向与路的方向一致。前向弧的全体记为P+；
后向弧——弧的方向与路的方向相反。后向弧的全体记为P-； 设F是一个可行流，P是从s到t的一条路，若P满足下列条件： 在P+的所有前向弧(u,v)上，0<=f(u,v) 1/3 1/3 S 1/1 B 0/4 D 图4.4 C 2/2 A 1/5 T 0/3 0/2 E 本图中：S-A-C-B-D-E-T为一增广路径。其中(C,B)为后向弧，其它为前向弧。 3) 增广路径上的改进算法 求路径可改进量； Cf(P)?min{前向弧C(u,v)?f(u,v) 、后向弧f(v,u)} (u,v)?P修改增广路径上的流量； 4) 残留网络 由于要考虑前向、后向弧，分析、描述时不简洁，直接在图上看也不容易看出增广路径。 因此我们把已经有的流量从容量中分离出来表示，引入一个与原问题等价的残留网络。 2 1 S 0 1 2 A 4 4 D 图4.5 C 2 1 0 1 T 3 2 B E 其中，前向弧(黑色)上的容量为“剩余容量”=C(u,v)-f(u,v)；后向弧(红色)上的容量为“可 第 6 页 共 15 页 59146965 福州一中 肖汉骏 退流量”=f(v，u)。 改造后的网如下： 2 A 1 4 4 D 图4.6 C 2 1 3 2 T 2 S 1 1 B E 在这张图上，我们找增广路径显的非常直观了! 结合增广路径，我们有如下定理： 最大流-最小割定理：如果残留网络上找不到增广路径，则当前流为最大流；反之，如果当前流不为最大流，则一定有增广路径。最大流值对应最小割。任何图中，从s到t的最大流等于所有(s,t)割的容量的最小值。 5) 算法流程 一般的Ford-Fulkerson方法具有迭代性质，我们把顶点u和v之间的流记作f(u,v)。那么在最开始，我们对所有的u,v∈V置f(u,v)=0。在每次的迭代过程中，通过找到一条增广路径来使|f|增加。在这里，我们可以简单地认为所谓的“增广路径”就是一条可以传送比当前更多流的从源点s到汇点t的路径，一旦找到了这样的路径，我们就可以得到一个比原流流量更大的新流。重复这个过程，直到不存在增广路径为止，这就是Ford-Fulkerson方法的主要过程，可以用伪码表示如下： FORD-FULKERSON-METHOD(G,s,t) 将流f初始化为0 while存在一条增广路径p do顺沿p增加f returnf 实现Ford-Fulkerson的时间复杂度主要取决于如何寻找增广路径p。常见的有深度搜索dfs、宽度搜索bfs以及优先搜索pfs——即类似Dijkstra算法的标号法。Edmonds-Karp实现正是通过采用了bfs的搜索策略得以使其复杂度达到O(V*E2)。 3. 一般性的push-relabel算法 很多渐进意义下最优的算法都是采用了push-relabel算法的思想，而且很多其他的相关问题，比如最小费用流问题，也可以用这种方法很好的解决。首先介绍的是一般性的push-relabel算法。 不同于Ford-Fulkerson方法在残留网络中寻找增广路径的方式，push-relabel算法在运行的过程中只关注某一个顶点以及它的相邻顶点，在这个过程中，它并不像Ford-Fulkerson方法保持着“流的保持”性质，而是以一个“先流”进行运作。这个先流同样是一个V×V→R的函数，满足容量限制和斜对称性，同时，它对所有的u∈V-{s}满足f(v,u)>=0。我们记e(u)=f(v,u)。如果e(u)>0我们就说顶点u溢出。 为了步入正题，我们还需要介绍push-relabel算法引入的一个额外的高度函数。设G=(V,E)是一个流网络，源点是s，汇点是t，f是G中的一个先流。如果函数h:V→N满足h(s)=|V|， 第 7 页 共 15 页 59146965 福州一中 肖汉骏 h(t)=0，而且对残留网络中所有的边(u,v)有h(u)<=h(v)+1，那么称h是一个高度函数。 正如其名称一样，push-relabel算法有两个基本操作:push和relabel。一般性的push-relabel算法就是通过往复执行这两种操作完成的： GENERIC-PUSH-RELABEL(G) 先流初始化 while存在可以执行的push或relabel操作 选择一个可以执行的push或relabel操作执行 下面具体介绍一下这两个基本操作。 可以执行的时机：顶点u溢出，u、v之间的残留容量cf(u,v)为正，且h[u]=h[v]+1 动作描述：将df(u,v)=min(e[u],cf(u,v))个单位的流从u压向v 具体步骤： PUSH(u,v) df(u,v)=min(e[u],cf(u,v)) f[u,v]=f[u,v]+df(u,v) f[v,u]=-f[u,v] e[u]=e[u]-df[u,v] e[v]=e[v]+df[u,v] 可以执行的时机：u溢出，且对所有的残留网络中的边(u,v),有h[u]<=h[v] 动作描述：增加u的高度 RELABEL(u) 具体步骤： h[u]=1+min{h[v]:(u,v)是残留网络中的边} 1) 普通实现 通过证明，在一般性的push-relabel算法执行过程中，relabel操作的执行次数小于2|V|，push操作的执行次数小于2|V||E|+4|V|3+4|E||V|2，而每个relabel操作的耗时在O(V)级，每个push的耗时在O(1)级，选择一个可以执行的操作也可以在O(1)内完成，因此，存在具体的实现使得一般性的push-relabel算法时间复杂度达到O(V2*E)。 2 2) relabel-to-front算法 通过引入邻接表和许可边的概念，relabel-to-front算法在push-relabel算法的基础上进一步提升了效率，使时间复杂度可以达到O(V3)，但是该算法的步骤和证明的过程比较繁琐，在这里就略去了，有兴趣的读者可以参考《算法导论》。 五、最大流问题的几种变形 1. 多源多汇问题 多源多汇问题的化归其实很容易想到——增设总源、总汇，很容易地转化为单源汇问题。 2. 点有容量问题 常用拆点法，一个点专门入边，另一个专门出边，入点向出点连一条边注明容量即可。 3. 多重边问题 多重边问题要具体分析，有的只要把容量累加即可，有的考虑到其它信息的不同（如费用等），或许还需要对边排序。若出现反向边，则定义2中的反向边容量不为0，须谨慎处理。 第 8 页 共 15 页