[ALDE 0x06] 网络流

01 网络流

流网络图是一种有向图，图中包含一个源点（source node）$s$ 和一个汇点（sink node）$t$，每条边都具有一个容量（capacity），该容量表示可以通过该边发送的最大流量。

网络流中存在两大主要问题——最小割问题和最大流问题。

• 最小割问题（minimum cut problem）的目标是找出将 $s$ 和 $t$ 分割的最小代价。

• 最大流问题（maximum flow problem）的目标是合理分配每条边的流量，找出从 $s$ 到 $t$ 可以发送的最大流量。

首先了解一下网络流中的割的定义。将顶点集划分为两个不交且非空的集合：

$$V = S \cup T, S \cap T = \varnothing$$

所有一端在 $S$，另一端在 $T$ 的边组成的集合称为一个割(cut)。我们将割中所有边的容量总和称为割的容量。关于割的记法，我们课上的记法为 $(S,T)$，这是从顶点的角度去描述割。

在最小割问题中，我们要寻找一个容量最小的割，将顶点集 $V$ 划分为两部分 $S$ 和 $T$，使得 $s \in S \land s \notin T$，$t \in T \land t \notin S$。

接下来了解一下网络流中的 $s-t$ 流的定义。一个 $s-t$ 流其实是一个函数 $f:E \to N^{* }$，其中 $E$ 是网络流的边集，$N^{*}$ 是非负自然数集，并且对于任意 $e \in E$，一定有 $0 \le f(e) \le c(e)$，其中 $c(e)$ 是 $e$ 的最大容量。$f(e) = n$ 表示向 $e$ 发送 $n$ 个单位的流量。

根据网络流的性质，一个顶点流出的流量一定等于流入它的流量，因此对于任意 $u \in V$，$f$ 一定满足：

$$\sum_{e \text{ in to }u}f(e) = \sum_{e \text{ out of }u}f(e)$$

我们定义一个流的容量为流出源点的流量，或流入汇点的流量：

$$v(f) = \sum_{e \text{ out of } s} f(e) = \sum_{e \text{ in to } t} f(e)$$

而最大流问题就是去找一个 $f$，使得 $v(f)$ 最大。

02 贪心思路

我们首先考虑一种贪心思路来解决最大流问题：

1. 初始时，对于网络流中所有 $e \in E$，有 $f(e)=0$。
2. 遍历所有 $s-t$ 路径，对于每条路径上的每一条边，都发送尽可能多的流量。

这种朴素的贪心思路的问题在于，流量一旦被发送就无法收回。它向每条边都发送当前能发送的最大流量，因此，它选择的第一条路径 $P_{1}$ 上的所有边 $e \in P_{1}$，一定有 $f(e)=\underset{e \in P_{1}}{\min} \\{ c(e) \\}$，这一点无法再改变；而此后遍历到的路径 $P_{i}$（$i \gt 1$）上的所有边 $e \in P_{i}$，则是 $f(e)=\underset{e \in P_{i}}{\min}\\{c(e)-f(e)\\}$。但最优的 $s-t$ 流可能不是像这样把所有流量一次性分配完，而是把一部份流量匀给其他。例如下图所示的情况：

为了解决贪心思路无法撤回已发送流量的问题，Ford-Fulkerson 算法引入了一种新的数据结构——残余图。

03 Ford-Fulkerson 算法

Ford-Fulkerson 算法通过引入残余图（residual graph）来获得撤回流量的能力。

在残余图 $G_{f}$ 中，对于网络流图 $G$ 中任意一对由边 $e=u \to v$ 连接起来的顶点 $u$ 和 $v$，在它们之间新增一条反向边 $e^{R}$。令 $c_{f}(e)$ 表示边 $e$ 的剩余容量，即 $c_{f}(e) = c(e) - f(e)$；令 $c_{f}(e^{R})$ 表示能撤回的流量（或者说已分配的流量），即 $c_{f}(e^{R}) = f(e)$。

Ford-Fulkerson 算法的执行流程：

1. 初始化 $s-t$ 流 $f$，令 $f(e)=0,\forall e \in E$，初始化残余图 $G_{f}$。
2. 从 $G_{f}$ 中选出一条 $s-t$ 路径 $P$，要求该路径上所有的边 $e$ 都要有 $c_{f}(e) \gt 0$，即满足 $\underset{e \in P}{\min} \\{ c_{f}(e) \\}\gt 0$，我们称这种路径为增广路径。
3. 向增广路径 $P$ 发送能发送的最大流量（这一步称为“增广”），即对于任意 $e \in P$：
   1. 若 $e$ 是一条正向边，令 $f(e)=f(e)+\underset{e \in P}{\min} \ c_{f}(e)$，并更新 $G_{f}$。
   2. 若 $e$ 是一条反向边，令 $f(e)=f(e)-\underset{e \in P}{\min} \ c_{f}(e)$，并更新 $G_{f}$。
4. 回到步骤 2，直到再无法找到任何一条增广路径为止，此时得到的 $f$ 就是最大 $s-t$ 流。

上述流程中出现的 $\underset{e \in P}{\min} \ c_{f}(e)$，我们一般称之为瓶颈，记为 $\Delta$。

Ford-Fulkerson 算法主要由寻找增广路径和增广操作两部分组成，增广操作是常数级别的，因此算法的复杂度主要集中在寻找增广路径，所以 Ford-Fulkerson 算法的时间复杂度可以表示为 $增广次数 \times 寻找一条增广路径的代价$。使用 DFS 或 BFS 寻找一条增广路径的代价是 $O(E)$，那增广次数呢？

算法在找不到增广路径时停止，也就是对于任意一条路径，在算法停止时，都有 $\Delta=0$。而 $\Delta$ 的最大值其实就是 $v(f^{* })$，即最大流的值。Ford-Fulkerson 算法的每轮循环都会使 $\Delta$ 变小，因此，增广次数其实是限制在 $v(f^{* })$ 内的。

综上所述，Ford-Fulkerson 算法的时间复杂度可以表示为 $O(E \cdot v(f^{* }))$。

04 最小割问题

Ford-Fulkerson 算法解决了最大流问题，同时也解决了最小割问题。最小割可以从 Ford-Fulkerson 算法结束时得到的残余图中导出，方法是：

1. 对任意 $e \in E_{G_{f}}$，如果满足 $c_{f}(e)=0$，视其为不可达。
2. 统计所有从 $s$ 出发能到达的顶点，组成顶点集 $S$。
3. 统计所有从 $t$ 出发能到达的顶点，组成顶点集 $T$。
4. $(S,T)$ 为一个最小割。

下面我们证明为什么这样得到的就是最小割。

当算法结束时，$G_{f}$ 中已不存在 $s-t$ 路径，因此 $s$ 和 $t$ 必定断裂，所以 $(S,T)$ 肯定是一个割。再根据最大流最小割原理（the max-flow min-cut theorem）：在一个流网络中，最大流的量等于最小割的量（充要条件）。因此，$(S,T)$ 肯定是最小割。

05 最大二分匹配

最大二分匹配问题是最大流的一种应用，其描述为：

给定一个二分图：

$$G=(L\cup R,E)$$

其中 $L$ 和 $R$ 是两个不相交的顶点集合，且

$$E \subseteq L\times R.$$

一个匹配是边集

$$M \subseteq E$$

满足任意两条边在 $M$ 中不共享端点，即：

$$\forall (u,v),(u',v')\in M,\quad u\neq u'\ \text{且}\ v\neq v'.$$

最大二分匹配问题是指：在所有匹配 $M$ 中，寻找一个匹配 $M^{* }$，使得

$$|M^{* }|=\max\{|M| \mid M \subseteq E,\ M \text{ 是匹配}\}.$$

我们将使用解决最大流问题的思路解决最大二分匹配问题。

首先，引入两个虚拟的源点 $s$ 和汇点 $t$，并对于任意 $u \in L$，新增边 $s \to u$；对于任意 $v \in R$，新增边 $v \to t$。我们令所有边的容量为 1。这样，我们就得到了一张网络流图 $G^{\prime}$。

根据网络流图的性质，流出每个顶点的流量必然等于流向这个顶点的流量。而对于 $L$ 和 $R$ 中的每一个顶点，流入它们的流量都为 1，那么流出的流量必然也为 1。因此，如果我们在 $G^{\prime}$ 上运行 Ford-Fulkerson 算法，对于任意 $u \in L$，在得到的最大流 $f$ 中，绝不会存在两个不同的顶点 $v_{1},v_{2} \in R$，使得 $f(\langle u,v_{1}\rangle)=f(\langle u,v_{2}\rangle)=1$，即不会发生一对多的冲突，否则就会使得从 $u$ 流出的流量大于 1.

并且，Ford-Fulkerson 算法得到的 $f$ 是最大流，这意味着它会在不发生冲突的情况下，尽可能多的去分配流量，而在 $G^{\prime}$ 中每条边的容量都是 1，因此，尽可能多的去分配流量就等价于尽可能多的去选择可用的边。综上所述，我们将得到以下结论：

$$\boxed{最大流值 = 最大匹配的大小}$$

那么如何输出找到的最大匹配方案？很简单，就是所有被发送了流量的边，即：

$$最大匹配=\{ e | e \in E \land f(e)=1 \}$$

如果，一个匹配 $M$ 中包含了所有二分图中的节点，即每个节点都被匹配，那么就称 $M$ 为一个完美匹配。

Hall 定理给出了完美匹配存在的条件：二分图 $G$ 存在一个完美匹配当且仅当对任意子集 $S\subseteq L$，都有 $|N(S)| \ge |S|$，其中 $N(S)$ 表示 $S$ 在 $R$ 中的邻居集合。