cnPhil ? 网络流知识讲解

网络流是图论中相当重要的一部分，也是计算机科学中比较难掌握的一类知识，在这我就给各位讲一讲网络流的有关知识。要注意的是，网络上，包括很多书籍中关于网络流的名词很容易被理解错，为了方便大家理解，我在这里对很多名词作了详尽解释。

网络流图是一个有向图，其中有的点只有出边（入度为0），而有的点只有入边（出度为0），在我们一般研究的网络流图中，入度为0的点一般只有一个，称之为源点（Source）通常标号为 s，出度为0的点也一般只有一个，称之为汇点（Sink）通常标号为 t。在我们研究的小部分网络流图中，有时候会有多个源点，也有时候会有多个汇点，这时候，我们为了更方便地研究问题，我们新增一个点，名为“超级源”，从这个超级源向每个源点分别发出一条边（权值∞），我们再新增一个点，名为“超级汇”，从每个汇点分别向这个超级汇发出一条边（权值∞）。这样原图的特性也保留了，我们也将问题简化了。值得注意的是，我们研究的网络流图都是连通赋权图。

首先网络流图是有向图，那么，我们用 (u,v) 表示从点 u 发出到点 v 的一条边（又称作一条弧）；同时，网络流图也是一个赋权图，那么每条边都会有一个权值了，我们将这个权值称为这条边的容量，我们把边 (u,v) 的容量记做   c(u,v) 。同时，我们联想到很多实际网络流问题，如物流问题，我们知道，每条边除容量之外还有一个实际流量，这个实际流量就是这条边实际分担的流。我们把边 (u,v) 的流量记为 f(u,v) 。对于网络流图中的任何一条边 (u,v) ，都满足 f(u,v)≤c(u,v) 。这是事实上就是网络流三大特性之一的容量限制特性。

在我们的图中，每一条边上都有形如“a / b”的标记，a 表示此边的流量，b 表示此边的容量，我们发现，的确每条边的流量都小于等于容量。

我们把一个形如“点 边 点 边 点 …… 点 边 点” 的序列叫做链，链必须是以点开头的，也必须是以点结尾的。链中的每条边的两旁都是点，而且必须是这条边连接的两个点。链的方向就是“从 u 到 v ”，但是，链对其中的边的方向是没有要求的，也就是说，一条从 u  到 v 的链，其中的边不一定要与“从 u 到 v ”同向，也就是说，链纯粹只是一个点边交替排列的序列，不一定要是一条连通的链。我们将一个链序列中与链同向的边叫做前向边，把链序列与链不同向的边叫做后向边。若一条链上全都是前向边，那么，这条链一定是连通的，我们叫这种链为单向链。在我们的图中，[s, (s,a), a, (a,c), c, (c,t), t] 是一条链而且是单向链，而 [s, (s,c), c, (c,t), t] 虽然是一条链但不是单向链，其中 (s,c) 为后向边，(c,t)为前向边。

我们看一个净流量值 ‘f(u,v) ，这个值是指 u 到 v 的净流的大小，即这个净流量值等于从 u 到 v 的所有流量和减去从 v 到 u 所有流量和，请注意，u 和 v 之间有可能没有边相连，但是，它们可能由于与其他的点相连而使得他们之间有流量（即存在以 u,v 为首尾的单向链），也就是说若实际中从 u 到 v 有10单位流量，从 v 到 u 有3单位流量，那么，我们说，从 u 到 v 有7单位净流量，即净流量 ‘f(u,v)=7 。同时我们可以把问题更加数学化一点，既然从 u 到 v 有净流量 ‘f(u,v) ，那么我是不是也可以看成从 v 到 u 有净流量 –’f(u,v) 呢？这是肯定可以的。我们可以写出如下很容易理解的公式： ‘f(v,u)=-’f(u,v) 。这事实上是网络流三大特性之二的斜对称特性，又叫反对称特性。

我们观察到，一个网络流图中，除了源点及汇点以外，所有的点都既有出边又有入边，我们称这样的点为中间点，我们容易知道，对于任何一个中间点 u ，都有 ( Σ’f(u,w) )=0，其中 w 是图中的所有点。通俗一点，实际上就是说对于每个中间点的流入流量等与其流出流量，我们称这为该点的净流为0 。这就是网络流三大特性之三的流守恒特性。

我们还可以定义边(u,v)的剩余流量c_f(u,v) = c(u,v) − f(u,v)。路径其实就是单向链序列，当路径上每相邻的两个点之间当前方向的边只有一条时，我们可以把路径序列中的边都去掉，使得路径序列变成一条点序列，在我们的图中，[s, a, c] 是其中一条路径。若这个路径[u₁,u₂,u₃ ... u_n] 满足 u₁=s 且 u_n=t 且 c_f(u_i,u_{i + 1}) > 0 (其中 1≤i≤n)，我们就叫这个路径为扩张路径，对于扩张路径，我们有一个修正值θ，使得每一条边的流量增加θ后其流量依然小于等于其容量，我们不难发现，修正值θ的最大值就等于整条扩张路径上所有边的剩余流量c_f的最小值。在我们的图中，[s, b, d, t] 是一条扩张路径，其修正值θ的最大值等于 c_f(d,t) =1 。

我们设有网络流图G=(V,E)， V 是其所有点的集合， E 是其所有边的集合。设 S₁, S₂ 是 V 的两个真子集，且满足 S₁∩S₂ =Ø , S₁∪S₂ =V, s∈S₁ , t∈S₂  . 设 A₁ 是 E 中所有两端点都在S₁中的边的集合，设 A₂ 是 E 中所有两端点都在S₂中的边的集合，设 A’=C_E(A₁∪A₂) ，即 A’ 是 A₁∪A₂ 在全集 E 中的补集。那么我们称 A’ 是关于(S₁, S₂)在图中的割集，简称割，记为 A’=(S₁, S₂) ，在我们的图中 { (a,c), (c,s), (b,d) } 就是一可行的割集，对于割集中所有始点在S₁中而终点在S₂中的“这样”的边（注意，在我们的图中，如果我们定义 S₁={ s, a, b } ，定义 S₂={ c, d, t } ，{ (a,c), (c,s), (b,d) } 为一可行的割集，其中 (c,s) 边不属于“这样”的边），“这样”的边的容量的和为割集 A’ 的容量，其实这样我们就把整个图抽象为两个点（两个区间），从源点区到汇点区的流量就是“这样”的边的流量和，从汇点区到源点区的流量就是割集 A’ 中不是“这样”的边的流量和。对应不同的S₁, S₂，其割集 A’ 的容量也不同。我们把在所有的割集中容量最小的割集称为最小割集，简称最小割。

还记得之前的净流量 ‘f 吗，现在，我们可以称其为流，满足上述网络流三大特性的流称为可行流，每个可行流都有一个源点，一个汇点，就像净流量符号 ‘f(u,v) 一样，事实上， ‘f(u,v) 就是从 u 到 v 的可行流的（净流量）大小，对应所有从 u 到 v 的可行流，其净流量最大的一个，叫做最大流。

定理：（最大流-最小割定理）一个网络流图的最大流大小等于其最小割的容量。这个定理很容易证明。

对于一条链，若其满足以下两个条件：

(1) 链上所有前向边的流量都没有达到其容量，即所有前向边都为非饱和边。

(2) 链上所有后向边的流量都不为零。

那么，我们把这样的链叫做可增广道，我们发现前面我们定义的扩张路径其实就是可增广道的特例，那么，对应的，我们也可以找到一个修正值θ，让每条前向边的流量增加θ，而每条后向边的流量减少θ，这样，可行流就增大了。在我们的图中，[s, (c,s), c, (c,t), t] 这样一个可增广道，我们可以找到一个修正值θ=1，让 (c,s) 的流量减少1，让 (c,t) 的流量增加1 。这样，可行流 (s,t) 的净流量就增大了1 ，我们把这样通过修正值θ修正的过程叫做增广。可增广道的神奇性质就在于，通过增广可增广道，一定可以使得可行流增大，而且，我们这样做还能维护这个流的可行性，请大家想一想，可增广路为什么一定能够增广呢？我们观察可增广路上这样的点：这个点的前一条是后向边，这个点的后一条是前向边；（如我们的图中的 c 点） 这样的点一定不会只连了这两条边，肯定还连了另外一条相对于可增广道是前向的边，否则这个点的前向流量是从何而来呢？所以，我们把那条前向的边给这个点的流量重新分配一下，给可增广道中的前向边多一点，给可增广道中的后向边少一点。就这样，可增广道中的没一条边都可以通过被这个修正值θ修正来增大可行流。

这样我们的除了这样的一个结论：只要是可增广道，我们一定就可以通过增广来增大可行流。换句话说，我们得到了如下定理：可行流 f 是最大流当且仅当不存在关于 f 的可增广道。

这样一条定理似乎告诉了我们一个求网络流中最大流的方法。事实上，以这个定理为基础的求最大流的 Ford-Fulkerson 算法 是一个求最大流的复杂度较优并且广泛使用的算法，当然求最大流还有很多各有千秋的算法，下面我来一一讲解。

基础的 Ford-Fulkerson 算法流程如下：（之所以连接 Ford 和 Fulkerson 这两个单词的是”-”而不是”·”，就是因为这不是一个人的全名，而是两个人的名字合在一起，就像 Bellman-Ford 算法一样）

1. 初始化一个可行流（一般是净流量为零的流）
2. 在可行流中找到一条可增广道，若找不到，则当前可行流为最大流，退出算法。
3. 找到适当的修正值θ增广该可增广道，所谓适当，就是维护该流可行性的最大可能值。
4. 执行 2.

这个算法的中找到可增广道的实现方法有很多，一般有 DFS, BFS ，其中 BFS 的效率较优于 DFS ，为O(VE²)。

基于以上算法的改进算法——标号法的主要流程如下：

1. 在一个可行流（一般是净流量为零的流）上，给源点 s 标号 (0,+ ,θ(∞) ) ，分别表示标号为0；正向流出；以及可增广能力为无穷。此时 s 是仅有的已标号但未检查的点，其余的点为未标号的点。
2. 若被标号的所有点均已检查过，此时该可行流就是最大流。否则到 3.
3. 任取一个已标号但未检查的点 u ，找到所有与 u 有边（方向不限）相连的点 v ，满足以下 a.b. 之一：
   

   a.  有边 (u,v) ，且 f(u,v)

   b.  有边 (v,u) ，且 f(v,u)>0 ，则给 v 点标号 (u, -, θ(v) ) ，其中 θ(v)=min( θ(u), f(v,u) )

   c.  若汇点 t 未被标号，则将 u 点标记为已检查，进入 2. ；否则，我们已经找到了一条完整的可增广道，令 q=t 进入以下增广过程。（进入 4. ）

4. 若 q 点的标记为 + ，为 (p, +, θ(q) ) ，则 f(p,q)=f(p,q)+θ(t)，否则 f(q,p)=f(q,p)-θ(t)
5. 若 q=s ，则去掉全部标记，转 1. ，否则转 4. 。

事实上，整个标号法就是在不断的找可增广道，然后增广，其实质就是 Ford-Fulkerson 算法。但是，我们有了一个副产品！在退出算法时，当前所有已标号且已检查的点所组成的集合 S1 就是网络流图的一个最小割 (S₁, S₂) 中的 S₁ ，也就是说，我们同时求出了网络流图的最小割之一。其时间复杂度依然为 O(VE²) ，但在常数上有优化。所以，其只适用于边较稀疏的网络流图。那么，对于边稠密的网络流图，我们有没有更佳的算法呢？我们下次将介绍时间复杂度分别为 O(V²E) 和 O(V³) 的两个算法。

好了，这些就是有关网络流的知识。最后在这新春佳节即将到来之际，我祝 cnPhil 的各位访客们来年学业进步，牛气冲天！