前置知识 · 分档取舍 · 依赖图

网络流的数学预备

这一页不讲算法，只回答一个问题：读这个系列之前该会什么。九项前置按用途分四档，前八项各自注明在哪一页兑现；末一项不挂任何一页，它标的是系列边界之外的方向（见 §6）。

1 · 按阅读目标取舍前置

九项前置不是齐头并进的门槛。只想实现一份能用的最大流，与想说清最大流为何等于最小割，需要的东西相差很远。

图 1-1 · 九项前置与各页的依赖关系。左列按分档着色，右列是各页；切换阅读目标可把范围外的页画淡，单击任一侧条目高亮它的全部连线。

依赖表是通读全系列后人工核定的，判据是「缺了它读不下去」，不是「正文提到过这个词」。原本打算用关键词命中自动生成，试了一轮就放弃：Hall 匹配到了参考文献里的出版社 Prentice Hall，ISAP 那页因此被判为需要 Hall 婚配定理，而它与匹配理论毫无关系；约束 也分不开「容量约束」与「线性规划的约束矩阵」，于是最大流那页被判为需要矩阵写法。术语密度高的文本上，关键词命中的假阳性比人工核定的成本更贵。

2 · 图论与复杂度的底座

有向图、路径、割、可达性、DAG 这五样是最低要求。残量网络本身就是一张有向图，割是顶点集的一个二分，Dinic 的层次图是 DAG。这些概念从第一页起就被当作已知使用。

复杂度那一侧真正要紧的不是会背 $O(V^2E)$ ，而是能跟上两类论证。第一类是把总代价拆成乘积：Dinic 的界来自「相位数 $\le V-1$ 」乘「单相位 $O(VE)$ 」，两个因子的来源完全不同，前者靠最短路长度单调递增，后者靠当前弧指针。第二类是计数式的摊还论证，形如「一条边在一个相位里只会被彻底尝试常数次」。这类论证在 Dinic 与 ISAP 两页反复出现，不习惯的话会觉得复杂度是凭空报出来的。

3 · 守恒与容量的矩阵写法

到了线性规划那页，网络流要被当成线性规划看。这不需要会解线性方程组，只需要能把两组约束翻译成矩阵形式：

\max\ \mathbf{1}^\top x \quad \text{s.t.} \quad Mx = 0,\quad 0 \le x \le c

其中 $x$ 是各边流量， $c$ 是容量向量， $M$ 是守恒约束的系数矩阵。

定义 0.1（点-边入射矩阵） 有向图 $G$ 的入射矩阵 $M$ 的行对应点、列对应边，且

M_{ve} = \begin{cases} +1 & e \text{ 从 } v \text{ 出发} \\ -1 & e \text{ 进入 } v \\ 0 & \text{其余} \end{cases}

每一列恰有一个 $+1$ 与一个 $-1$ ， $Mx = 0$ 就是「每点流入等于流出」。

这个矩阵是后面两节的共同对象：对偶从它的转置读出，整数性从它的子式读出。

4 · 对偶与互补松弛

线性规划对偶要用的部分只有三条结论，且每一条在网络流里都有具体形态。

弱对偶说任何可行解的目标值不超过对偶可行解的目标值。落到网络流上就是「任何可行流的流量 $\le$ 任何 s-t 割的容量」——这一条不需要 LP 理论也能直接证：流量必须整体穿过割。它给出的是上下界夹逼的框架。

强对偶说两侧最优值相等。落下来正是 max-flow min-cut 定理，也就是最大流最小割定理那页的主结论。这一条是有内容的：它保证夹逼一定收紧到重合，而不只是留一道间隙。

互补松弛说最优解处每对「原始变量 / 对偶约束」中至多一个不紧。落下来是线性规划那页 §5 那组对应：未饱和的边不在割中，割中的边必然饱和。它把「最优」这个抽象条件翻译成可以逐边检查的局部条件。

三条里前两条支撑最小割那页，第三条支撑 LP 对偶那页。只读算法部分的话，这一节可以整节跳过。

5 · 全幺模与整数解

网络流有一条容易被当作理所当然的性质：整数容量下最大流一定取到整数值，而线性规划的解本可以是分数。这既不是巧合，也不是算法的功劳。算法只是没有制造分数，真正的原因在约束矩阵的结构。

定义 0.2（全幺模） 整数矩阵 $A$ 称为全幺模（totally unimodular），若它的每一个方阵子式的行列式都属于 $\{-1, 0, +1\}$ 。

定理 0.3（Hoffman–Kruskal） 设 $A$ 全幺模、 $b$ 与 $c$ 为整数向量，则多面体 $\{x : Ax = b,\ 0 \le x \le c\}$ 的每个顶点都是整数点。

线性规划的最优值必在顶点取到，所以整数容量下的最大流有整数最优解。剩下要验的只有一件事：入射矩阵是否全幺模。

证明（入射矩阵全幺模）对子式阶数 $k$ 归纳。 $k = 1$ 时子式就是单个元素，取值已在 $\{-1,0,1\}$ 。设 $k > 1$ ，任取一个 $k$ 阶子式 $S$ 。若 $S$ 有一列全零，则 $\det S = 0$ 。若 $S$ 有一列只含一个非零元 $\pm 1$ ，按该列展开， $\det S = \pm \det S'$ ， $S'$ 是 $k-1$ 阶子式，由归纳假设其行列式在 $\{-1,0,1\}$ 内。否则 $S$ 的每一列都保留了原矩阵那一列的两个非零元，即每列同时含一个 $+1$ 与一个 $-1$ ，各列之和为零向量， $S$ 的行线性相关， $\det S = 0$ 。∎

证明里的三种情形都是可枚举验证的，不必只当作纸上推导。

图 5-1 · 入射矩阵的方阵子式枚举。可选网络与子式阶数 k，在非零子式之间翻看，或关掉「保留边的方向」看全幺模如何失效。行列式走整数消元，取值是精确判定而非浮点近似。

搁浅网的入射矩阵是 $6 \times 8 $，$ k$ 从 1 到 6 共有 3002 个方阵子式，其中 896 个行列式非零，全部为 $\pm 1$ ，其余 2106 个为 0。

方向性是这条性质的必要前提，而「入射矩阵全幺模」这句话在转述时很容易把它漏掉。把边的方向去掉后，每列变成两个 $+1$ ，上面证明的第三种情形立刻失效——列和不再为零。实测三个点的有向环无向化后，3 阶子式的行列式是 $\pm 2$ ，全幺模不成立；而四个点的环（二部图）无向化后仍然全幺模。无向图的入射矩阵全幺模当且仅当图是二部的，这一条与 König 定理属于同一族结论。

实现这一节的验证代码时踩了一个与数学无关的坑：整数消元在奇异子式上算出的是 $-0$ ，而 Object.is(-0, 0) 为假，「行列式落在 $\{-1,0,1\}$ 内」这类按值比较的断言会莫名失败。det 的出口现在把负零折回 0。

6 · 建模手法与势能法

余下三项前置的性质与前面几节不同，它们更像手活而非定理。

归约手法是建模那三页的主要内容，靠量堆出来：拆点处理点容量、虚拟源汇处理多源多汇、下界转成附加流量、最大权闭合子图处理取舍类问题。这部分没有可背的原理，判断力来自见过足够多的建图方案。

势能法用来读懂两件事为何终止。ISAP 的距离标号与 HLPP 的高度都是势函数：单调不减、有上界，操作次数必然有限。最小费用流那页里，Johnson 重标号用同一手法把负权边消成非负，好让 Dijkstra 能用。认出「这是个势函数」之后，这三处的终止性论证是同一个论证。

极小极大定理族（König、Hall、Menger、Dilworth）都是 max-flow min-cut 的特例或近亲。读懂本系列并不需要它们，它们是读完之后的红利：认出一道题属于这一族，就能省掉一次重新证明。

至于凸分析与群流，本系列用不到。凸代价流是最小费用流往外的推广方向，群流与流和着色之间的对偶属于图论那条线，图论合集的流一页有介绍。列在依赖图里只是为了标出边界。

本页读完即可直接进最大流与残量网络。§3 到 §5 的内容在读到最小割那页之前都用不上，回头再看不影响前面几页。

7 · 参考文献

Hoffman, A. J., & Kruskal, J. B. (1956). Integral boundary points of convex polyhedra. In H. W. Kuhn & A. W. Tucker (Eds.), Linear Inequalities and Related Systems (pp. 223–246). Princeton University Press.
Schrijver, A. (1986). Theory of Linear and Integer Programming. Wiley.
Ahuja, R. K., Magnanti, T. L., & Orlin, J. B. (1993). Network Flows: Theory, Algorithms, and Applications. Prentice Hall.
Schrijver, A. (2003). Combinatorial Optimization: Polyhedra and Efficiency. Springer.