算法设计与分析（实验班）复习笔记

Posted on Edited on

Abstract. 仅 Focus 在当年学 OI 的时候没有重视的网络流复杂度分析、下界计算、近似比计算等。

最大流

本节中，记一个容量网络为一个五元组 $N = \langle V, E, c, s, t\rangle$，其中 $V$ 为点集，$E\subset V \times V \setminus {(v, v) : v\in V}$ 为有向边的集合，$c : E\rightarrow \mathbb{R}^*$ 为流量，$s, t$ 为源点汇点。默认读者熟悉诸网络流的问题描述、线性规划形式。任意一个可行流的流量记作 $v(f)$。

最小割最大流定理

本节揭示最大流问题与网络最小割问题的深刻关联，顺带介绍和分析 Ford-Fulkerson 算法。当然，为了证明最小割最大流定理，有一个极其丑陋的线性规划对偶加调整的证法，这里从另一个方向考虑。

定义 1（割集）. 网络 $N$ 的一个基于 $A\subset V$（须满足 $s\in A, t\notin A$）的割集记作

$$
(A, \bar{A}) := { (u, v) \in E : u\in A, v\in \bar{A} }
$$

其容量为

$$
c(A, \bar{A}) := \sum_{e\in (A, \bar{A})} c(e)
$$

将源汇割开之后，一个可行流的流量正好是割集上的流量。具体地

引理 1. 对于任意可行流 $f$ 和割集 $(A, \bar{A})$，都有

$$
v(f) = \sum_{(u, v) : u\in A, v\in \bar{A}} f(u, v) - \sum_{(u, v) : u\in \bar{A}, v\in A} f(u, v)
$$

证明. 用节点流量守恒将流量推至割集边缘即可。$\blacksquare$

这自然推出可行流和割集的弱对偶性和互补松弛条件。

推论 2. 对于任意可行流 $f$ 和割集 $(A, \bar{A})$，都有

$$
v(f) \leq c(A, \bar{A})
$$

取等当且仅当 $f$ 是最大流，$(A, \bar{A})$ 是最小割。

Ford-Fulkerson 算法的出发点是图论中常见的增广路思想，本质上是一种反悔贪心。我们首先从增广路的定义开始。

定义 2（增广路）. 网络 $N$ 上的一条 $i, j$-路系指一个途径点的序列 $i = p_1, p_2, …, p_k = j$ 配上对应的边 $e_1, …, e_{k - 1}$，满足 $e_t = (p_t, p_{t + 1})$ 或 $e_t = (p_{t + 1}, p_t)$。满足前者的边称作前向边（边方向和链前进方向相等），满足后者的边称作后向边。

如果序列中的任意前向边 $e_f$ 都未满流即 $f(e_f) < c(e_f)$，任意后向边 $e_b$ 都非空即 $f(e_b) > 0$，则该路径为 $i, j$-增广路。

引理 3. $f$ 是最大流当且仅当图中不存在 $s, t$-增广路。

证明. 必要性显然。下证充分性。

令 $A$ 表示全体 $j$，使得存在 $s, j$-增广路。考虑一条割边 $(i, j)$。

  1. 若 $i\in A, j\in \bar{A}$，则 $f(i, j) = c(i, j)$，否则 $j\in A$；
  2. 若 $i\in \bar{A}, j\in A$，则 $f(i, j) = 0$，否则 $i\in A$。

由引理 1，$v(f) = c(A, \bar{A})$，进而由引理 2，$f$ 是最大流，$(A, \bar{A})$ 是最小割。$\blacksquare$

至此，为了证明最小割最大流定理，只需要证明确实存在一种 $f$ 使得图中不存在 $s, t$-增广路即可。有一众基于增广路的网络流算法都可以构造出这个流，因此我们证明了如下定理：

定理 4（最小割最大流定理）. 一个网络 $N$ 的最小割等于其最大流。

基于增广路的算法

接下来介绍一众基于增广路的算法，包括 Ford-Fulkerson，Edmonds-Karp，Dinic，ISAP。这些算法系依次改进而来，其核心思路都是出于图论上的直觉，即每次增广一条路径。

算法 1（Ford-Fulkerson）. 重复用 dfs 找增广路，若找到就尝试增广使得一条前向边满流或者一条后向边零流。直到找不到时停止。

该算法每次找到增广路流量必增加，流量有上界。在只有整数流量时，算法复杂度为 $O(E|f^*|)$。然而，在有无理数流量时，可能发生无穷次增广，最后答案收敛在最大流。

为此提出的改进导出了 EK 算法。首先为了方便实现算法，定义网络 $N$ 在可行流 $f$ 上的残量网络：

定义 3（残量网络）. 网络 $N$ 在可行流 $f$ 上的残量网络的边集和对应容量由以下构造给出：若 $N$ 中有边 $(u,v)$，流量为 $c(u, v)$，则 $N(t)$ 中将增加边 $(u, v)$，流量为 $c(u, v) - f(u, v)$ 和 $(v, u)$，流量为 $f(u, v)$。

容易发现以下几个基本事实：

  1. $N(f)$ 上任意一条不满流的路径和 $N$ 上的一条增广路一一对应。
  2. $N(f)$ 上任意一个可行流 $g$ 对应 $N$ 上一个可行流 $f’$，其中 $v(f’) = v(f) + v(g)$，且 $$
    f’(u, v) = f(u, v) + g(u, v) - g(v, u)
    $$
  3. 一轮增广之后，残量网络的变化可以高效计算。

因此我们只需在残量网络上操作。另外定义

定义 4（分层辅助网络）. 网络 $N$ 在可行流 $f$ 上的分层辅助网络 $AN(f)$ 是保留所有 $N(f)$ 中满足 $d(v) = d(u) + 1$ 的边（$d(u)$ 表示从 $s$ 出发仅经过非满流边到 $u$ 的最短路长度）得到的网络。很明显，这是一个有向无环图。

EK 算法即是强制每次增广必须增广最短的那条增广路的 Ford-Fulkerson 算法。换言之，每次增广的路径必须在 $AN(f)$ 上。

考察每次增广之后分层辅助网络的变化。

  1. $AN(f)$ 上的边可能因为满流而被从 $N(f)$ 中删去，进而被从 $N(f)$ 中删去。这可能导致某些点 $u$ 的 $d(u)$ 增大。
  2. $AN(f)$ 上的边的反向边可能原为零容量，但在增广之后容量增加进而加入 $N(f)$。但是只要 $d(u)$ 没有发生变化，这条反向边就不会加入 $AN(f)$，因为

则至多 $|E|$ 次增广后，将至少有一个点 $u$ 的 $d(u)$ 增大。每次增广时间为 $O(|E|)$，$d(u)$ 增大的次数至多为 $O(|V|^2)$。因此 EK 算法的时间复杂度为 $O(V^2E^2)$（无论流量是整数还是实数）。

似乎还可以分析的更细一点。如果一条边 $(u, v)$ 被删掉了又被加回了 $AN$，则这表明其反向边进入了 $AN$，此时 $d’(v) \geq d(v), d’(u) = d(v’) + 1 \geq d(u) + 2$，这蕴含总增广次数不超过 $EV / 2$。这样可以分析出一个 $O(VE^2)$ 的复杂度。

当然，这里还存在改进的空间。如果每次在 $AN(f)$ 上做多路增广，似乎可以节省复杂度。这就是 Dinic 算法的动机。为此，我们定义一个极大流为不存在仅包含前向边的 $s, t$-增广路的可行流。容易对 $d(u)$ 归纳证明，Dinic 里的那个当前弧优化的 dfs 能求出 $AN(f)$ 上的一个极大流。

再分析一下当前弧优化的复杂度。该算法实际上就是每次用 $O(V)$ 的时间（而非 $O(E)$ 时间，因为过程中动态维护了第一条能走通的出边）找一条 $s, t$-路，然后删掉上面一条边。因此复杂度为 $O(VE)$。

注意，增广一个极大流之后，必有 $d(t)$ 增大。这个事件发生的次数至多为 $V$。因此，Dinic 算法的复杂度为 $O(V^2E)$。

这一段是口胡的批话。

上课没有讲过的一个网络流优化是 ISAP 算法。这个算法的动机是动态维护 $d(u)$（从而动态诱导出），节省 bfs 次数。首先 $d(u)$ 是从 $s$ 出发来的最短路还是到 $t$ 的最短路不影响分层性质，所以我们跑到 $t$ 的最短路以便后续实现。dfs 的时候，如果发现一个点的流量没有用完，说明它出发已经不能从现在的 $AN$ 走到 $t$ 了，于是我们将其 $d$ 加 $1$。如果 $d$ 出现了断层，则停止算法。

这个算法并不能分析出更好的界，但是实际上快很多。

基于预流推进的算法

另一类网络流算法基于物理直觉：模拟往网络上灌水的过程。受此启发，我们首先定义“预流” $f$ 为原网络流问题对应线性规划的线性规划：只要求

  1. $f(u, v) \leq c(u, v)$；
  2. 每个节点的流入量大于等于流出量，即除 $s$ 外所有点 $i$ 都满足 $$
    \sum_{(u, i)} f(u, i) - \sum_{(i, v)} f(i, v)
    $$

记每个节点的溢出量（上述约束不等式的左边）为 $e(u)$。每次选择一个 $e(u) > 0$ 的非汇点，将其溢出量沿着残量网络上的出边推到它的邻居（流量不得超过容量）。因为残量网络上反向边的存在性，多余的流量可以流回 $s$。

这样可能会出现在两个点之间来回推流的情况，因此用类似于 Dinic 的办法给图分层，为每个节点定义一个高度 $h(u)$，规定推流只能从高度为 $h + 1$ 的点推至高度为 $h$ 的点。但这样还是会有问题，可以想象无论如何初始化，都会出现某时刻存在某点仍然溢出，但是不能向周围任意一个点推流的情况（比如说把分层辅助网络全部推满流之后），因此还需要对点进行重标号。

形式化地，我们定义下面两个操作：

算法 2（预流推进）. $\text{Push}(u, v)$：应用条件为 $e(u) > 0, c_f(u, v) > 0$。这里容量系残量网络上的容量。

令 $\Delta(u, v) := \min(e(u), c_f(u, v))$。更新预流为：若 $(u, v)$ 为正向边，让 $f(u, v)$ 加上 $\Delta(u, v)$，若 $(u, v)$ 为反向边，让 $f(u, v)$ 减去 $\Delta(u, v)$。

对于此操作，若 $\Delta(u, v) = c_f(u, v)$，则称为饱和推进，否则称不饱和推进。

算法 3（重标号）. $\text{Relabel}(u)$：应用条件为 $e(u) > 0$ 且 $u$ 在残量网络上的任意邻居 $v$ 都满足 $h(u) \leq h(v)$。

将 $h(u)$ 置为 $\min_v h(v) + 1$。

则下面的算法将能够求出网络最大流：

算法 4（预流推进算法）.

  1. 初始化 $h(s) = V$，其余 $h(u) = 0$；$e(u) = +\infty$；
  2. $\mathrm{Push}(s)$；
  3. 重复以下两步骤，直到无法操作：
  4. 若 $(u, v)$ 满足 $\mathrm{Push}(u, v)$ 的条件，执行之；
  5. 若 $u\ne s, t$ 满足 $\mathrm{Relabel}(u, v)$ 的条件，执行之。

答案是 $e(t)$。

这个算法非常符合直觉，但是无论是时间还是正确性的分析都非常阴间。

引理 1. 算法执行过程中 $h(u)$ 单调递增，且每次 relabel 至少使其增加 $1$。

证明. 显然。$\blacksquare$

注意，下面所说的残量网络都是不计容量为 $0$ 的边的。

引理 2. 算法执行过程中，以下条件始终满足：

$$
\forall (u, v)\in N(f), \quad h(v) + 1 \geq h(u)
$$

证明. 施归纳于算法过程。考虑两个操作对 $N(f), h(u), h(v)$ 各自的影响。

  1. 预流推进操作可能会让一条边从残量网络中消失或者增加反向边。根据预流推进操作的条件，执行后条件仍然满足。
  2. 重标号操作可能会改变 $h(u)$，但是根据其流程此条件仍然满足。

$\blacksquare$

引理 3. 残量网络中始终不存在 $s$ 到 $t$ 的路径。

证明. 假设存在路径，则根据引理 2 可推得 $h(u) \leq V - 1$，与其初值矛盾。$\blacksquare$

引理 4. 若算法终止，则算法求出最大流。

证明. 若算法终止，则 $f$ 是可行流（除源、汇外，都有 $e(u) = 0$）。而且根据引理 $3$，图上没有增广路，因此该可行流是最大流。$\blacksquare$

引理 5. 算法执行中任意节点的高度 $h(u) \leq 2V - 1$。

证明. 因为 $s$ 的高度锁死为 $V$，再根据引理 2 立即得到结论。$\blacksquare$

事实上引理 5 和引理 1 几乎能表明算法将停止。我们现在来详细分析算法的复杂度。

引理 6. 算法执行中：

  1. 重标号操作至多发生 $V^2$ 次；
  2. 饱和推进至多发生 $O(VE)$ 次；
  3. 不饱和推进至多发生 $O(V^2E)$ 次。

证明. 第一条根据 $h(u)$ 的值域和重标号的影响立即得证。

第二条类似于 EK 算法的分析，若一条边上发生了一次饱和推进，下次推进它之前必然依次对 $v, u$ 进行了重标号，因此 $h(u)$ 将增加 $2$，再根据 $h$ 有上界，可知每条边最多推进 $V$ 次，总共最多推进 $VE$ 次。

第三条考虑记账法，定义

$$
\Phi = \sum_{e(i) > 0} h(i)
$$

每次饱和推进、重标号都将使得 $\Phi$ 至多增加 $O(V)$，而每次非饱和推进至少使其减少 $1$。因此非饱和推进次数为 $O(V^2(V + E)) = O(V^2E)$。$\blacksquare$

至此，我们证明了

定理 7. 通用预流推进算法在 $O(V^2E)$ 时间内算出网络的最大流。

如果时间充裕，我可能还想学一把最高标号预流推进的 $O(V^2\sqrt E)$ 是怎么来的，可惜我现在火烧眉毛了，所以我不学了。

费用流

两种算法：

  1. 消圈算法. 先求最大流，然后 Bellman Ford 找负环。
  2. MCMF 算法. 每次增广最短路。

前者适用于一切情况，后者仅在初始不存在负环时能证明是对的，方法都很 trivial，这里不写。

课件上说可以用 Dijkstra 算法跑费用流，但你可能还需要一些额外的操作，因为 Dijkstra 不能跑负权图。

经典的操作是对于每个点维护一个势能 $h(u)$，将边权置为 $w(u, v) + h(u) - h(v)$。这样一来，因为在路径上势能会发生邻项相消，所以最短路还是最短路。只需要保证 $w(u, v) + h(u) \geq h(v)$ 即可。容易想到，可以将 $h$ 设置为上一把的最短路，此时图中原有的边因为三角形不等式满足上述性质，在因为增广而新引入的负权边上三角形不等式是紧的，因此也满足此性质。