[数据结构与算法]网络流问题

1 网络流问题

我们从问题的定义开始。给定一个简单有向图 $G$、一个源节点 $s$ 和一个汇节点 $t$。回想一下，一个简单的图不包含平行边（一对具有相同顶点且指向同一方向的边）和环（从顶点到自身的边）。我们假设图的每个顶点都可以从 $s$ 到达，并且 $t$ 可以从图的每个顶点到达，所以没有“无用”的顶点。$G$ 中的每条边 $e$ 都有一个关联的非负容量 $c(e)$。例如，假设我们想要将消息流从源路由到终点，容量告诉我们每条边允许多少带宽。例如，考虑下面的图 1 。

我们的目标是在图中将尽可能多的流从 $s$ 推到 $t$。规则是任何边的流量都不能超过其容量，对于除 $s$ 和 $t$ 之外的任何顶点，流入顶点的流量必须等于流出顶点的流量。即，

容量限制： 对于任意边 $e$，有 $0\le f(e)\le c(e).$
流量守恒： 对于任意顶点 v ? { s , t } v?\{s,t\} v∈/?{s,t}，流入量等于流出量：${\sum }_{u}f(u,v)={\sum }_{u}f(v,u).$

满足这些约束的流称为可行流。受限于这些约束，我们希望最大化从 $s$ 到 $t$ 的净流量。我们可以通过数量来正式衡量这一点
$$|f|=\sum _{u}f(s,u)?\sum _{u}f(u,s)$$
请注意，我们在这里测量的是来自 $s$ 的净流量。由于守恒，很容易证明它等于进入 $t$ 的净流量。

例如，在上图中，从 $s$ 到 $t$ 的最大流量是多少？答案： 5。使用“容量[流量]”表示法，正流量如图 2 所示。请注意，流可以自己分割和重新汇聚。

我们在上面定义流量 $f$ 的方式有时被称为总流量公式，我们将每条边 $e$ 上的非负流量衡量为 $0\le f(e)\le c(e)$。有时使用的另一种公式称为净流量公式。我们允许流量 $f(u,v)$ 为负，以表示流在给定边的相反方向上流动。这意味着对于所有 $(u,v)\in E$，我们定义 $f(v,u)=?f(u,v)$。这种性质称为反对称。请注意，这与上述问题没有不同，只是定义流的方式略有不同。所有的定理和算法在两个版本中的工作方式完全相同，所有这些变化都是一些定义和证明中的一些小细节。

在这个公式中，守恒约束也可以简化为 ? v ? { s , t } , ∑ u f ( u , v ) = 0 ?v?\{s, t\}, \sum _uf(u, v) = 0 ?v∈/?{s,t},∑u?f(u,v)=0，因为流出一个节点的总流量总是流入该节点总流量的负数。类似地，流量的值可以通过 $|f|={\sum }_{u}f(s,u)$来衡量, 因为所有流入的流量现在都被反对称定义视为负流量。

除非另有说明，否则将使用总流量公式来编写内容，因为它更明确，并且更易于使用。

1.1 提高流量：$s?t$ 路径

假设我们从最简单的流开始，即全零流。这个流显然是可行的，因为它满足容量限制，并且所有顶点的流入等于流出。但对于图 1 中的网络，全零流显然不是最优的。我们可以推理为什么它不是最优的吗？一种方法是观察到图中存在一条从 $s$ 到 $t$ 的路径，该路径由具有可用容量的边组成（实际上有很多这样的路径）。例如，路径 $s\to a\to c\to t$ 至少有 2 个可用容量，因此我们可以在不违反容量约束的情况下向每条边添加 2 个流，并提高了流量，如图3所示。

我们刚刚所做的一个重要观察是，如果向路径上的所有边添加恒定数量的流，永远不会违反流量守恒条件，因为每个顶点添加的流量都相同，除了 $s$ 和 $t$。只要不超过任何边的容量，由此产生的流仍然是可行流。

这一观察使我们得出以下想法：如果存在具有可用容量的 $s?t$ 路径，则流不是最优的。在上图中，我们可以观察到路径 $s\to b\to d\to t$ 还有 2 个可用容量单位，因此向边中添加了 2 个单位的流。最后，我们可以发现 $s\to a\to c\to b\to d\to t$ 路径多了 1 个单位的可用容量，我们可以从图 2 中得出最大流量。

1.2 证明流的最优性：$s?t$ 分割

刚刚看到了如何说服自己一个流量不是最大的，但是你怎么确定上面的流量真的是最大的呢？我们还不能确定我们没有做出错误的决定并沿着次优路径发送流。这里有一个想法。请注意，该流使边 $a\to c$ 和边 $s\to b$ 饱和，并且，如果删除这些边， $t$ 与 $s$ 会断开。换句话说，该图有一个大小为 5 的“$s?t$ 分割”（一组总容量为 5 的边，如果删除这些边，会使得源节点与汇节点失去连接）。这里的关键在于，从 $s$ 到 $t$ 的任何单位流量必须在这些边中占据至少 1 个单位的容量。所以，我们知道我们是最优的。

我想要说明的是，任何流量都小于任何 $s?t$ 分割的大小。由于每个流量最多为最大流，我们可以认为，一般来说，最大 $s?t$ 流 $\le$ 最小 $s?t$ 分割大小，或者 任何 $s?t$ 流 $\le$ 最大 $s?t$ 流 $\le$ 最小 $s?t$ 分割大小 $\le$ 任何 $s?t$ 分割大小。

流的一个重要属性，即最大 $s?t$ 流实际上等于最小 $s?t$ 分割的容量。这称为 Maxflow-Mincut 定理。事实上，算法会找到一个具有某个值 $k$ 的流和一个容量 $k$ 的分割，并证明两者都是最优的。

为了描述算法和分析，对其中一些量进行更正式的描述会有所帮助。

定义1 \quad 一个 $s?t$ 分割是一组边，删除它们会使 $t$ 与 $s$ 断开。或者，正式地，分割是将顶点集划分为两个部分 $S$ 和 $T$，其中 $s\in S$ 和 $t\in T$。（分割的边是从 $S$ 到 $T$ 的所有边）。

定义2 \quad 分割 $(S,T)$ 的容量是分割中边容量的总和。或者，从正式的角度来看，它是从 $s$ 到 $t$ 的所有边的容量之和。
$$cap(S,T)=\sum _{u\in S}\sum _{v\in T}c(u,v).$$
请注意，重要的是，我们在此定义中不包括从 $T$ 到 $S$ 的边。

定义3 \quad 流经分割 $(S,T)$ 的净流量是从 $S$ 到 $T$ 的流量之和减去从 $T$ 到 $S$ 的流量，或者更正式地说
$$f(S,T)=\sum _{u\in S}\sum _{v\in T}f(u,v)?\sum _{u\in S}\sum _{v\in T}f(v,u).$$
从这个定义中，我们可以看到一个流的值 $|f|$ 等于通过分割 ( { s } , V \ { s } ) (\{s\},V\backslash\{s\}) ({s},V\{s}) 的净流量。事实上，使用流量守恒性质，不难证明通过任何分割的净流量等于流量值 $|f|$。这应该是直观的，因为无论我们在哪里切割图形，从 $s$ 到 $t$ 的流量仍然相同。

1.3 寻找一个最大流

我们如何找到最大流并证明它是正确的？我们应该尝试将上面的两个想法联系在一起。这是一个非常自然的策略：找到一条从 $s$ 到 $t$ 的路径，并在其上推送尽可能多的流。然后查看剩余容量（一个重要问题是我们如何准确定义它）并重复，直到不再有任何路径有能力推送任何额外的流量。当然，我们需要证明这是可行的：我们不能在此过程中做出错误的选择而以某种方式最终得到一个次优的解决方案。对于简单地搜索具有可用容量的 $s?t$ 路径并为其添加流的简单算法，是否属于这种情况？不幸的是，事实并非如此。考虑下图，其中算法决定将 1 个单位的流添加到路径 $s\to a\to b\to t$。

是否有剩余可用容量的 $s?t$ 路径？没有。但是这个流的流量最大吗？也不是，因为我们可以从 $s\to a\to t$ 发送 1 个单位的流量，从 $s\to b\to t$ 发送 1 个单位的流量，总流量为 2。

这种尝试方案的问题在于，将流从 $a$ 发送到 $b$ 是一个“错误”，会降低网络中的可用容量。为了达到最大流量，我们需要一种“撤销”此类错误的方法。我们通过定义剩余容量的概念来实现这一点，该概念既说明了边的剩余容量，又增加了撤销错误决策并将次优流重定向到更优流的能力。这为我们引出了 Ford-Fulkerson 算法。

2 Ford-Fulkerson 算法

Ford-Fulkerson 算法简单如下：当存在正剩余容量的 $s\to t$ 路径 $P$ 时，沿 $P$ 尽最大可能推送流。顺便说一句，这些路径 $P$ 称为增广路径，因为使用它们来扩充现有流。

剩余容量只是在给定现有流的情况下的剩余容量，还表明了将现有流回推并沿着不同路径推送以撤消先前的错误决策的能力。

定义4 \quad 给定图 $G$ 中的流 $f$，剩余容量 $c_f(u,v)$被定义为
$$c_f(u,v)=\{\begin{array}{rlr}c(u,v)?f(u,v)& & if(u,v)\in E,\\ f(v,u)& & if(v,u)\in E.\end{array}$$
定义5 \quad 给定图 $G$ 中的流 $f$，剩余图 $G_f$ 是有向图，其所有边都有正剩余容量，每条边都由其剩余容量标记。注意：这可能包括原始图 $G$ 的反向边。

当 $(u,v)\in E$ 时，边的剩余容量对应于先前的“剩余”容量的直观概念，它是我们在边填充满之前可以添加的流量。第二种情况是使 Ford-Fulkerson 算法起作用的关键。如果 $f(v,u)$ 流已经被发送到某个边 $(v,u)$，那么我们可以通过将流发送回相反的方向 $(u,v)$ 来撤消它！例如，如果我们考虑图 4 中的次优流，剩余图如下所示。

请注意，与以前不同，现在有一条容量为 1 的 $s?t$ 路径！路径 $s\to b\to a\to t$ “撤消”最初通过 $a\to b$ 推送的流并将其重定向到 $a\to t$，从而提高流量并使其最优。

处理反平行边 \quad 如果我们假设图包含反平行边，剩余容量的定义会变得有趣。回想一下，平行边是具有相同端点 u 和 v 且指向同一方向的边，而反平行边是具有相同端点但指向相反方向的边。在这种情况下，可能是 $(u,v)\in E$ 且 $(v,u)\in E$，那么我们将这两种情况中的哪一种用于剩余容量？简单的答案是我们应该同时使用两者。我们可以选择将两者组合成一条边，并标识它们的容量之和，或者在剩余图中包含一对平行边。这两个选项都很好，并且在理论和实践中都有效。

让我们看另一个例子。考虑图 1，假设我们在路径 $s\to b\to c\to t$ 上推送两个单元的流。然后我们最终得到以下剩余图：

请注意，边 $c\to b$ 的容量为 3 是由于原始图中的边 $c\to b$ 容量为 1，加上由于 $f$ 从 $b\to c$ 经过2个单位的流从而产生可撤销的2单位剩余容量。我们也可以将它们绘制为容量 1 和 2 的两条独立边，但将它们组合起来通常更简单，这样我们就不会得到任何平行边。

如果我们继续执行 Ford-Fulkerson，我们会看到在这张图中，我们可以用来增加现有流的唯一路径是路径 $s\to a\to c\to b\to d\to t$。在这条路径上推送最多 3 个单位，我们得到下一个剩余图，如图 7 所示。

此时不再有从 $s$ 到 $t$ 的路径，所以我们完成了。

我们可以将 Ford-Fulkerson 视为在每个步骤中找到一个新流（沿着增广路径）并将其添加到现有流中。剩余容量的定义确保了 Ford-Fulkerson 找到的流是合法的（不超过原始图中的容量约束）。

我们现在需要证明它实际上是最大流。我们会考虑它需要的迭代次数以及如何改进。

请注意，剩余图的一个良好特性是，在每一步中，我们都会遇到与开始时相同类型的问题。因此，为了实现 Ford-Fulkerson，我们可以使用任何黑盒寻路方法（例如 DFS）。

2.1 分析

现在，我们假设所有容量都是整数。如果最大流量值为 $F$，则该算法最多进行 $F$ 次迭代，因为每次迭代都会将至少一个以上单位的流从 $s$ 推送到 $t$。我们可以使用 DFS 在 $O(m+n)$ 时间内实现每次迭代。由于我们假设图很简单，$m\ge n?1$，所以是 $O(m)$，所以我们得到以下结果。

定理6 \quad 如果给定的图 $G$ 具有整数容量，则 Ford-Fulkerson 的执行时间为 $O(mF)$，其中 $F$ 是最大 $s?t$ 流的值。

定理7 \quad 当它结束时，Ford-Fulkerson 算法输出一个流，其值等于图的最小分割。

证明： 让我们看看最终的剩余图。由于 Ford-Fulkerson 循环直到不再有从 $s$ 到 $t$ 的路径，所以该图必须使 $s$ 和 $t$ 断开，否则算法将继续循环。令 $S$ 为剩余图中仍可从 $s$ 到达的顶点集，$T$ 为其余顶点。必须保证 $t\in T$，否则 $s$ 与 $t$ 连通，这才是一个有效的 $s?t$ 分割。设 $c=cap(S,T)$，表示原始图中分割的容量。从我们之前的讨论中，我们知道 $|f|=f(S,T)\le c$。

假设我们实际上确实找到了值为 $c$ 的流（因此意味着它是最大流）。考虑 $G$ 所有在任一方向上跨越分割的边（原始图）。我们考虑两种情况：

1. 考虑 $G$ 中沿 $S\to T$ 方向跨越分割的边。我们认为这些边都达到了最大容量（已饱和）。假设有一条从 $S$ 跨越到 $T$ 的边不是饱和的。然后，根据剩余容量的定义，剩余图将包含一条从 $S$ 到 $T$ 具有正剩余容量的边，但这与 $T$ 包含剩余图中无法到达的顶点这一事实相矛盾，因为我们可以使用这条边到达 $T$ 中的一个顶点。因此，我们可以得出结论，从$S$ 到 $T$ 的每个跨越分割的边都是饱和的。
2. 考虑 $G$ 中沿 $T$ 到 $S$ 方向跨越分割的边。我们认为这些边都是空的（它们的流量为零）。同样，假设该判断不正确，并且存在 $T$ 到 $S$ 的边含有非零流。然后根据剩余容量的定义，将有一条从 $S$ 到 $T$ 具有正剩余容量的反向边。再次，这是一个矛盾，因为这意味着在剩余图中有一种方法可以到达 $T$ 中的一个顶点。因此，从 $T$ 跨越到 $S$ 的每条边都是空的。

因此，对于从 $S$ 到 $T$ 的每条跨越分割的边，$f(u,v)=c(u,v)$，对于从 T 到 S 的每条边， f(u, v) = 0，所以流经切口的净流量等于切口的容量 c.由于每个流的值最多是最小割的容量，因此这个割实际上必须是最小割，并且流的值等于它。