上下文

一个流网络是一个有向图，其中每条边可以表示一种通道、管道或导管，物质可以通过它流动。因此，流网络可以用来建模石油或水的分配网络。它还可以用于建模供需场景、交通拥堵情况，并且基本上可以应用于许多符合物质流动概念的实际情境。

每个问题中的流网络可能略有不同。通常，网络中的每条边或每个顶点都会关联一些数值。

问题设置

在本课中，我们介绍两个问题：最大流问题和最小割问题。但在描述这些问题之前，我们需要先引入一些术语。

• 一个流网络是一个有向图 $G=(V,E)$，其中每条边都关联一个称为该边容量的数值。边 $e$ 的容量记作 $C(e)$。当一条边表示为有序对 $(u,v)$ 时，其容量记作 $C(u,v)$。边 $e$ 的容量 $C(e)$ 表示由 $e$ 所代表的物理通道的最大通过能力。我们假设每条边 $e$ 都满足 $C(e) \geq 0$。

我们可能会疑惑：为什么不继续使用“带权有向图”这一说法，而改用“流网络”？简短的回答是：这是传统习惯。

• 我们假设一个流网络只有一个源点（source）顶点，物质从这里流出，以及一个汇点（sink）顶点，物质流入这里。源点和汇点分别记作 $s$ 和 $t$。

• 所有既不是源点也不是汇点的顶点称为中间顶点。

下图展示了一个流网络的例子，边上的标签表示容量。

什么是流？

网络中的流最好用一个函数 $f$ 来表达，该函数为每条边分配一个数值量。对于给定的流函数 $f$，边 $e$ 或 $(u,v)$ 上的流记作 $f(e)$ 或 $f(u,v)$。

注意：流网络中的流并不是网络定义的一部分，因为不同时刻可以通过网络流动的物质数量可以不同。因此，一个流网络可以对应多个合法的流函数。

为了使函数 $f$ 能够合理地表达“流”的概念，我们施加以下约束条件：

1. 我们做出一个常识性假设：每条边 $e$ 上的流是非负的，并且不超过该边的容量：

   $$\begin{align*} f(e) &\geq 0 \\ f(e) &\leq C(e) \end{align*}$$

2. 对于任意不是源点或汇点的顶点 $v$，流入 $v$ 的流量必须等于从 $v$ 流出的流量。换句话说，流在中间顶点上是守恒的。

如何理解边上的标签

在本章的插图中，一条边上显示两个数值 $f(e)$ 和 $C(e)$，这可能会引起混淆。请记住：较小的数代表流。我们采用将这两个数值以逗号分隔的形式表示：$f(e), C(e)$。

注意：当网络中没有流时，我们只在边上标注容量。

下面的例子使用这种视觉提示来展示一个具有明确流的网络。请注意，每条边上的流都被限制在其容量之内，并且所有顶点（除了源点 $s$ 和汇点 $t$）的流都是守恒的。

流的值

严格来说——根据流的定义——某些进入源点的边可能具有非零流。

我们将从源点净流出的流量（即流出量减去流入量）称为流的值。流 $f$ 的值记作 $Val_f$。

例如，在上述图示中，流的值为 2，因为从 $s$ 流出的总量为 2，而 $s$ 没有流入。

流的测验

让我们确认一下是否理解了基本定义。

什么是割？

在流网络的语境中，割表示网络中的一处横截面，物质必须经过这个横截面才能从源点到达汇点。形式上，如果我们把网络的顶点集 $V$ 划分为两个集合 $V_1$ 和 $V_2$，使得 $V_1$ 包含源点 $s$，$V_2$ 包含汇点 $t$，那么从 $V_1$ 中的顶点指向 $V_2$ 中顶点的所有边组成的集合称为一个割 $\langle V_1, V_2\rangle$。

例如，如下所示的流网络中存在一个割 $\langle V_1, V_2\rangle$，其中 $V_1 = \{s, v_1, v_2\}$，$V_2 = \{v_3, v_4, v_5, t\}$。这些割边已在图中高亮显示。

注意：如果移除从 $V_1$ 到 $V_2$ 的所有边，则物质将无法从 $s$ 流向 $t$。从 $V_1$ 到 $V_2$ 的边的容量之和称为该割的容量，记作 $C\langle V_1, V_2 \rangle$。例如，上图中割 $\langle V_1, V_2\rangle$ 的容量为 17。

割的容量对能通过该割的物质总量设定了上限。

重要的性质

给定一个流网络中的流 $f$，由于 $f$ 在所有中间顶点上守恒，从源点 $s$ 净流出的流量 $Val_f$ 等于进入汇点 $t$ 的净流量。同样，流的值必须等于任何割 $\langle V_1, V_2\rangle$ 的净流量，其中 $s \in V_1$ 且 $t \in V_2$，因为这部分净流量必须穿过该割才能到达汇点。

因此，流的值不可能超过任意一个割中所有边容量的总和。我们将其表述为：

$$Val_f \leq C\langle V_1, V_2 \rangle$$

这个不等式非常关键，我们将在后续看到它的价值。

检验理解

让我们做一个小测验，看看是否真正掌握了所学内容。

对偶问题

对偶问题是本质上互为两面的问题。在本章中，我们介绍以下两个相互对偶的优化问题。

最大流问题

给定一个流网络 $G$，最大流问题的目标是找到一个在 $G$ 中具有最大值 $Val_f$ 的流 $f$。

一个具有最大值的流称为最大流（max flow）。

最小割问题

给定一个流网络 $G$，最小割问题的目标是找到一个容量最小的割 $\langle V_1, V_2\rangle$，即在所有可能的割中容量最小的那个。

容量最小的割称为最小割（min cut）。

本章介绍的算法，称为Ford-Fulkerson 算法，不仅能求出流网络中的最大流，还能同时找出最小割。该算法适用于单源单汇的网络，但很容易扩展到包含多个源点和多个汇点的情况。

一个约定与一些技巧

需要注意的是，应用 Ford-Fulkerson 算法的流网络被假定为任意一对顶点 $u$ 和 $v$ 之间最多只有一条边。

• 在现实世界中遇到的物理网络对应的流网络中，若同一对顶点间存在多条边，可以通过拆分处理。拆分一条边 $(u,v)$ 指的是将其替换为两条边 $(u,x)$ 和 $(x,v)$，其中 $x$ 是新创建的顶点，且新边继承原边的容量。

通过这种方式，我们可以对修改后的网络运行 Ford-Fulkerson 算法，从而得到最大流；而修改后网络的最大流也对应于原始网络（存在多条边的情况）的最大流。