网络流模型总结福州一中肖汉骏【引言】：➢“许多问题可以先转化为网络流问题，再运用最大流算法加以解决。

而发现问题本质，根据最大流算法的特点，设计与之相配的数学模型是运用最大流算法解决问题的重要步骤。

”➢“网络流在具体问题中的应用，最具挑战性的部分是模型的构造。

这没用现成的模式可以套用，需要对各种网络流的性质了如指掌（比如点有容量、容量有上下限、多重边等等），并且归纳总结一些经验，发挥我们的创造性。

”➢注：本文大部分出自江涛老师讲稿及网络资料D3S A B C T E 3 2 1 4 2 3 5 图1.1【理论部分】： 一、引入如同我们可以把一个实际的道路地图抽象成一个有向图来计算两点之间的最短路径，我们也可以将一个有向图看作一个流网络来解决另一类型的问题。

流网络比较适合用来模拟液体流经管道、电流在电路网络中的运动、信息网络中信息的传递等等类似的过程。

一个实例：运输网络参看下图，给定一个有向图G=(V ,E)，把图中的边看作管道，每条边上有一个权值，表示该管道的流量上限。

给定源点s 和汇点t ，现在假设在s 处有一个水源，t 处有一个蓄水池，问从s 到t 的最大水流量是多少，类似于这类的问题都可归结为网络流问题。

在流网络中，每条有向边可以被看导管。

每根导管有一个固定的容量，代表物质流经这个导管的最大速率，例如一个管道每小时最多能流过200加仑液体或者一根电线最多能承载20安培的电流。

流网络中的顶点可以看作是导管的连接处。

除了源点和汇点之外，物质流进每个点的速率必须等于流出这个点的速率。

如果我们把研究的物质特化为电流，这种“流的保持”属性就好像电路中的基尔霍夫电流定律一样。

二、网络流相关定义1网络定义：➢ 一个有向图 G=(V ，E)；➢ 有两个特别的点：源点s 、汇点t ；➢ 图中每条边(u,v)∈E ，有一个非负值的容量C(u,v) 记为 G=(V ，E ，C)，网络三要素：点、边、容量可行流定义：是网络G 上的一个“流”，即每条边上有个“流量”P(u,v)，要满足下面两个条件：流的容量限制——弧：),(),(0v u C v u P ≤≤ 对任意弧(u,v)---有向边流的平衡限制——点：除源点和汇点，对任意中间点有：流入u 的“流量”与流出u 的“流量”相等。

即：{,}(,)(,)0x Vx Vu V s t P x u P u x ∈∈∀∈--=∑∑有网络的割：一个s-t 割是这样一个边的集合，把这些边从网络中删除之后，s 到t 就不可达了。

或者，正式的说，一个割把顶点集合分成A,B 两个集合，其中s 在A 中,t 在B 中，而割中的边就是所有从A 出发，到达B 的所有边。

割的容量就是割中所有边的容量的和。

正式的说，就是所有从A 到B 的边的容量的和。

网络的流量：源点的净流出“流量” 或 汇点的净流入“流量”。

即：∑∑∑∑∈∈∈∈-=-Vx Vx Vx Vx x t P t x P s x P x s P ),(),(),(),(注意，我们这里说的流量是一种速率，而不是指总量。

联系上面所说的实例，下面是一个流量为1的可行流：图2.2三、网络流相关定义2下面我们用数学语言来进行相关概念的定义：设G=(V,E)是一个流网络，设c(u,v)>＝0表示从u到v的管道的流量上限。

设s为源，t处理最小费用最大流，则反向边的费用为正向边的费用的相反数。

四、解决最大流问题常用算法一览1. 预览寻找网络G上可能的最大流量(和一个有最大流量的可行流方案)，即为网络G上的最大流问题。

它是网络流问题中最基本的问题，而网络流问题又可以归结为一类特殊的线性规划问题。

解决最大流问题的常用到Ford-Fulkerson方法，之所以称其方法而不是算法，是因为在这种思想下包含着若干种时间复杂度不同的实现，其中较多地是使用Edmonds-Karp算法。

与此相对，Push-relabel算法采用了与Ford-Fulkerson方法完全不同的思考角度，降低了渐进意义下的时间复杂度。

而relabel-to-front算法则是对Push-relabel算法的改良和精炼，效率更佳。

关于这三种常用算法的时间复杂度可见下表：（其中V表示图的顶点数，E表示边数）可以看出，当给定的有向图比较稀疏时，三种算法的效率不会相差太多，但当网络稠密时，relabel-to-front算法在效率上有着明显的优势。

图4.12. Ford-Fulkerson 方法求解过程中的困惑：[问题1]流量还可能增加吗？ [问题2]如果能增加，怎样改进？ 退流的概念——后向弧仔细分析图4.1，我们发现，流量是可以增加的：把一个流量弧(B,C)和(C,T)上的流退回到B 点，改道从B-D-E-T 走，就可以增加流量了，如下图：图4.1不能“直接寻找增大流的路径”，是因为当初有些弧上的流选择不“恰当”，要“退流”。

一种直观的想法就是：调整或重新搜索“当初的选择”——难！ 能不能保留以前的工作，而在这之上改进呢？经过专家们研究发现，加入退流思想——后向弧，就能再次“直接寻找增大流的路径”。

2) 增广路径(可改进路径)的定义若P 是网络中连结源点s 和汇点t 的一条路，我们定义路的方向是从s 到t ，则路上的弧有两种：前向弧——弧的方向与路的方向一致。

前向弧的全体记为P+； 后向弧——弧的方向与路的方向相反。

后向弧的全体记为P-； 设F 是一个可行流，P 是从s 到t 的一条路，若P 满足下列条件： 在P+的所有前向弧(u,v)上，0<=f(u,v)<C(u,v); 在P-的所有后向弧(u,v)上，0<f(u,v)<=C(u,v);则称P 是关于可行流F 的一条可增广路径。

本图中：S-A-C-B-D-E-T 为一增广路径。

其中(C,B)为后向弧，其它为前向弧。

3) 增广路径上的改进算法求路径可改进量；}u)f(v, ),(),({min )(),(、后向弧前向弧v u f v u C P C Pv u f -=∈修改增广路径上的流量；4) 残留网络由于要考虑前向、后向弧，分析、描述时不简洁，直接在图上看也不容易看出增广路径。

因此我们把已经有的流量从容量中分离出来表示，引入一个与原问题等价的残留网络。

其中，前向弧(黑色)上的容量为“剩余容量”=C(u,v)-f(u,v)；后向弧(红色)上的容量为“可退流量”=f(v，u)。

在这张图上，我们找增广路径显的非常直观了!结合增广路径，我们有如下定理：最大流-最小割定理：如果残留网络上找不到增广路径，则当前流为最大流；反之，如果当前流不为最大流，则一定有增广路径。

最大流值对应最小割。

任何图中，从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初始化为0while存在一条增广路径pdo顺沿p增加freturnf实现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|，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操作执行下面具体介绍一下这两个基本操作。

1)普通实现通过证明，在一般性的push-relabel算法执行过程中，relabel操作的执行次数小于2|V|2，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)relabel-to-front算法通过引入邻接表和许可边的概念，relabel-to-front算法在push-relabel算法的基础上进一步提升了效率，使时间复杂度可以达到O(V3)，但是该算法的步骤和证明的过程比较繁琐，在这里就略去了，有兴趣的读者可以参考《算法导论》。

五、最大流问题的几种变形1. 多源多汇问题多源多汇问题的化归其实很容易想到——增设总源、总汇，很容易地转化为单源汇问题。

2. 点有容量问题常用拆点法，一个点专门入边，另一个专门出边，入点向出点连一条边注明容量即可。

3. 多重边问题多重边问题要具体分析，有的只要把容量累加即可，有的考虑到其它信息的不同（如费用等），或许还需要对边排序。

若出现反向边，则定义2中的反向边容量不为0，须谨慎处理。