企业官网建设流程全解析

• 文档
• 教程
• 教育

导读：本节是《算法导论》（Introduction to Algorithms, Third Edition）第 26 章"最大流"中的第 3 小节，主题是把二分图最大匹配（maximum bipartite matching）归约为最大流问题，再用 Ford-Fulkerson 方法求解。本文以 docs/Chap26/26.3.md 的 5 道习题解答为主体，完整展开增广路径的逐步执行、整数性定理（Theorem 26.10）的归纳证明、Hall 定理与 d-正则二分图的匹配存在性证明，并结合 CLRS 仓库中 26.1、26.2、26.4、26.5 及 第 26 章 Problem 26-1 至 26-6 的源码级材料做纵深佐证。读完你将掌握：如何构造二分匹配对应的流网络、为什么匹配与流一一对应、如何在残量网络上手工推演 Ford-Fulkerson，以及如何用最大流-最小割与整数性把组合匹配问题化归为流问题。

26.3 节核心理论：把二分匹配归约为最大流

在进入习题之前，先建立本节依赖的理论骨架。给定无向二分图 $G = (V, E)$，顶点划分为 $V = L \cup R$，且每条边恰好有一个端点在 $L$ 中。CLRS 26.3 节构造了对应的流网络 $G' = (V', E')$：

• 顶点集 $V' = V \cup {s, t}$，其中 $s$ 为源点、$t$ 为汇点；
• 边集 $E' = {(s, u) : u \in L} \cup {(u, v) : (u, v) \in E,\ u \in L,\ v \in R} \cup {(v, t) : v \in R}$；
• 所有边的容量均设为 $1$。

该构造的思想是：一条从 $s$ 经某个 $u \in L$、某条原始边 $(u, v)$、再到某个 $v \in R$ 最后抵达 $t$ 的单位流量路径，恰好对应匹配中的一条边 $(u, v)$。由于每条 $L \to R$ 的边容量为 1、每个 $L$ 顶点只能收到 1 个单位来自 $s$ 的流量、每个 $R$ 顶点只能送出 1 个单位到 $t$ 的流量，任何整数值流都自动满足"匹配"要求的边不相交性（顶点互不冲突）。仓库 docs/Chap26/26.2.md 中 26.2-7 对增广流 $f_p$ 满足容量约束与守恒律的证明，正是理解"单位路径 = 单位匹配边"的基础。

本节依赖的四个关键结论（均出现在本小节习题的证明中）：

从复杂度看，由于 $|f^*| \le |V|$，且每次增广流值严格增加 1（整数性与单位容量），Ford-Fulkerson 最多执行 $|V|$ 次增广、每次用 BFS/DFS 在 $O(E)$ 内找增广路径，因此二分图最大匹配的总运行时间为 $O(VE)$。仓库 docs/Chap26/Problems/26-2.md 在最小路径覆盖的解答中明确引用了这一结论（"section 26.3 tells us that we can find a maximum flow in $O(V E)$"），可以作为复杂度声明的仓库内证据。

习题 26.3-1：在图 26.8(c) 上逐步执行 Ford-Fulkerson

题目：在图 26.8(c) 所示的流网络上运行 Ford-Fulkerson 算法，并在每次流量增广后画出残量网络。将 $L$ 中的顶点自上而下编号为 $1$ 到 $5$，$R$ 中的顶点自上而下编号为 $6$ 到 $9$。在每一轮迭代中，选择字典序最小的增广路径。

解答思路：顶点编号规则决定了字典序的比较方式——路径序列越靠前的顶点编号越小，路径越"小"。因此增广路径的选取顺序完全由 $L$ 侧顶点编号主导。本仓库给出的执行过程为：

1. 第一轮：选取经过顶点 $1$ 和 $6$ 的增广路径，即 $s \to 1 \to 6 \to t$。由于所有边容量为 1，此次增广量为 $1$，匹配中新增边 $(1, 6)$。
2. 第二轮：选取经过顶点 $2$ 和 $8$ 的增广路径，即 $s \to 2 \to 8 \to t$，增广量为 $1$，匹配中新增边 $(2, 8)$。
3. 第三轮：选取经过顶点 $3$ 和 $7$ 的增广路径，即 $s \to 3 \to 7 \to t$，增广量为 $1$，匹配中新增边 $(3, 7)$。
4. 终止：三轮增广之后，残量网络中已不存在从 $s$ 到 $t$ 的路径，算法终止。

最终得到的匹配为顶点对 $(1, 6)$、$(2, 8)$、$(3, 7)$，共 3 条边。为了验证这就是最大匹配，仓库解答采用了一个干净的割论证：考虑割断边 $(s, 3)$、$(6, t)$、$(7, t)$ 所定义的割，其容量为 $3$——即 $S$ 侧包含 ${s, 1, 2, 4, 5, 6, 7}$、$T$ 侧包含 ${3, 8, 9, t}$ 的划分（割断的恰为源点连向顶点 3 的边、以及顶点 6 与 7 连向汇点的边）。该割的容量恰好等于已找到的 3 条单位增广路径的总流量，由最大流-最小割定理，这说明所得流即为最大流，匹配 ${(1, 6), (2, 8), (3, 7)}$ 即为最大匹配。

手工推演要点：在单位容量网络中，每轮增广后都要检查残量网络：正向边容量耗尽后反向边出现（残量容量为 1），而未被使用的边保持原状。当且仅当残量网络中仍存在 $s$ 到 $t$ 的路径时才继续增广；一旦路径消失，就可用一个与之容量相等的割（如本例的容量 3 的割）来证明最优性。

习题 26.3-2：归纳法证明整数性定理（定理 26.10）

题目：证明定理 26.10（整数性定理）。

定理陈述（由 26.3 小节上下文可得）：若容量函数 $c$ 只取整数值，则 Ford-Fulkerson 方法产生的最大流 $f$ 满足 $|f|$ 为整数；且对所有顶点 $u, v$，$f(u, v)$ 的值为整数。

证明（对 Ford-Fulkerson 的 while 循环迭代次数归纳）：

• 基础步：第一轮迭代开始时，由于 $c$ 只取整数值，且初始化时 $(u, v).f = 0$（整数），因此残量容量 $c_f$ 只取整数值。于是 Ford-Fulkerson 伪代码中第 7、8 行只会把整数值赋给 $(u, v).f$。
• 归纳假设：假设第 $n$ 轮迭代后，对所有 $(u, v) \in E$ 都有 $(u, v).f \in \mathbb{Z}$。
• 归纳步：在第 $n + 1$ 轮迭代中，$c_f(p)$ 被设为 $\min_{(u, v) \in p} c_f(u, v)$。由于残量容量是"原容量减去当前流"，而原容量与当前流均为整数，由归纳假设 $c_f(u, v)$ 仍为整数，故 $c_f(p)$ 为整数。第 7、8 行计算的 $(u, v).f$ 或 $(v, u).f$，本质上是整数的和或差，因此第 $n + 1$ 轮迭代后，对所有 $(u, v) \in E$，$(u, v).f$ 仍为整数。

由于流值 $|f|$ 是所有离开源点的边流之和，而这些边流都是整数，故 $|f| \in \mathbb{Z}$。证毕。

为什么这个定理对 26.3 节如此关键：二分匹配流网络中所有容量为 1，整数性保证每次增广量恰为 1（而非 0 到 1 之间的某个分数），从而"一条增广路径 = 匹配中的一条新边"成立，也保证了增广次数上界为 $|V|$ 及 $O(VE)$ 的运行时间。仓库 docs/Chap26/Problems/26-5.md（容量缩放最大流）也反复使用"容量为整数则增广路径容量为整数"这一事实（其 c 部分"所有原容量为整数，因此任何增广路径容量不小于 1"），可视为本定理在全章问题中的再次应用。

习题 26.3-3：增广路径长度的上界（仓库标注 Removed）

题目：设 $G = (V, E)$ 为顶点划分 $V = L \cup R$ 的二分图，$G'$ 为其对应的流网络。给出 $\text{FORD-FULKERSON}$ 执行过程中在 $G'$ 中发现的任意增广路径长度的良好上界。

本仓库 docs/Chap26/26.3.md 对该题的解答明确标注为(Removed)，即维护者选择不提供解答。可以依据流网络结构做如下结构推断（非仓库给出的官方答案）：$G'$ 中任意简单增广路径的形态为 $s \to L \to R \to L \to R \to \cdots \to t$，顶点在 $L$ 与 $R$ 之间交替，且路径是简单的（不重复经过顶点），因此长度（边数）以 $O(|V|)$ 为平凡上界；同时，正是这种"交替走反向边以取消旧匹配"的形态，使得二分图匹配语境下的增广路径与匹配的对称差操作（见 Problems/26-6.md 中 Hopcroft-Karp 问题对匹配增广路径的定义与性质证明）之间建立了联系。

习题 26.3-4：证明 Hall 定理（完美匹配存在的充要条件）

题目：称匹配为完美匹配（perfect matching），若每个顶点都被匹配。设 $G = (V, E)$ 为无向二分图，顶点划分 $V = L \cup R$，且 $|L| = |R|$。对任意 $X \subseteq V$，定义 $X$ 的**邻域（neighborhood）**为

$$N(X) = {y \in V : (x, y) \in E \text{ 对某个 } x \in X},$$

即与 $X$ 中某顶点相邻的顶点集合。证明Hall 定理：$G$ 中存在完美匹配，当且仅当对 $L$ 的每个子集 $A$，都有 $|A| \le |N(A)|$。

证明（必要性与充分性）：

（$\Rightarrow$）必要性：假设 $G$ 中存在完美匹配。则对任意子集 $A \subseteq L$，$A$ 中每个顶点都与 $R$ 中某个邻居匹配；又因为是匹配，任意两个这样的顶点不会匹配到 $R$ 中的同一个顶点。因此 $N(A)$ 中至少有 $|A|$ 个顶点，即 $|A| \le |N(A)|$。

（$\Leftarrow$）充分性：假设对所有 $A \subseteq L$ 都有 $|A| \le |N(A)|$。在对应流网络上运行 Ford-Fulkerson。由于每次找到增广路径，流值增加 $1$（单位容量 + 整数性），只需证明增广会发生 $|L|$ 次。

反设 while 循环运行次数少于 $|L|$ 时，已不存在增广路径。此时 $L$ 到 $R$ 之间流量为 $1$ 的边少于 $|L|$ 条。

• 取 $v_1 \in L$，使得从 $v_1$ 到 $R$ 中任何顶点的边流量均为 $0$（即 $v_1$ 尚未匹配）。由假设 $N({v_1}) \ge 1$，$v_1$ 至少有一个邻居 $v_1' \in R$。
• 若 $v_1$ 的某个邻居与 $t$ 在 $G_f$ 中相连，则 $s \to v_1 \to v_1' \to t$ 即为增广路径，矛盾；因此 $v_1$ 的每个邻居到 $t$ 的边都已饱和，即 $v_1'$ 已被某个 $L$ 顶点匹配。换言之，存在 $v_2 \in L$（$v_2 \ne v_1$）使得边 $(v_2, v_1')$ 流量为 $1$。
• 由假设 $N({v_1, v_2}) \ge 2$，存在 $v_2' \ne v_1'$ 且 $v_2' \in N({v_1, v_2})$。若 $(v_2', t)$ 是残量网络中的边，则由于 $v_2'$ 必是 $v_2$ 的邻居（且边 $(v_2, v_2')$ 未满载，因为 $v_2$ 仅有的 1 单位流量输出在 $(v_2, v_1')$ 上），得到 $G_f$ 中的路径 $s, v_1, v_1', v_2, v_2', t$，即增广路径，完成证明。否则 $(v_2', t)$ 已饱和，$v_2'$ 必有邻居 $v_3 \in L$ 使得 $(v_3, v_2')$ 在 $G_f$ 中、流量为 $1$。具体地：
  • $v_3 \ne v_1$：因为 $(v_3, v_2')$ 流量为 $1$，而 $v_1$ 没有任何带正流的出边；
  • $v_3 \ne v_2$：因为 $(v_2, v_1')$ 流量已为 $1$，在流量守恒约束下 $v_2$ 不能再输出流量。
• 再次由假设 $N({v_1, v_2, v_3}) \ge 3$，存在新的邻居 $v_3' \in R$。如此往复，我们不断构造邻域顶点 $v_i'$，每次发现 $(v_i', t)$ 不是 $G_f$ 中的边时就继续扩展。

这个构造过程不可能持续 $|L|$ 次：因为我们运行 Ford-Fulkerson 的 while 循环次数少于 $|L|$，$G_f$ 中仍存在进入 $t$ 的边（仍有未被匹配满的 $R$ 顶点）。因此过程必然在某个顶点 $v_k'$ 处停止，从而得到增广路径

$$s, v_1, v_1', v_2, v_2', v_3, \ldots, v_k, v_k', t,$$

与"不存在这样的路径"的假设矛盾。

于是 while 循环至少运行 $|L|$ 次。由推论 26.3，流值每次严格增加 $f_p$；由定理 26.10，$f_p$ 为整数；在单位容量网络下 $f_p$ 恰为 $1$。因此 $|f| \ge |L|$。又显然 $|f| \le |L|$（源点 $s$ 只有 $|L|$ 条容量为 $1$ 的出边），故 $|f| = |L|$。由推论 26.11，这正是最大匹配的基数；又因 $|L| = |R|$，任何最大匹配必为完美匹配。证毕。

直观解读：Hall 条件是二分图存在完美匹配的组合学判据，本证明通过最大流将其转化为一个"贪心扩展"论证——每当某个 $R$ 顶点已饱和（被占用），就能顺着反向残量边回溯到新的 $L$ 顶点，再用 Hall 条件保证邻域足够大、总能找到新的出路；由于总存在未饱和的 $R$ 顶点，回溯必然终止于一条完整增广路径。

习题 26.3-5：d-正则二分图存在基数为 $|L|$ 的匹配

题目：称二分图 $G = (V, E)$（$V = L \cup R$）为$d$-正则（$d$-regular）的，若每个顶点 $v \in V$ 的度数恰好为 $d$。每个 $d$-正则二分图满足 $|L| = |R|$。证明：每个 $d$-正则二分图都有基数为 $|L|$ 的匹配——论证其对应流网络的最小割容量为 $|L|$。

证明思路：先把二分图转化为流问题：新增源点，源点到每个 $L$ 顶点连单位容量边；新增汇点，每个 $R$ 顶点到汇点连单位容量边；$L$ 与 $R$ 之间保留原始边（单位容量）。我们的目标是证明割的两部分之间的边数至少为 $|L|$，这样由最大流-最小割定理，存在流值至少为 $|L|$ 的流；再应用整数性定理（所有流值为整数），意味着在 $L$ 与 $R$ 之间选取了 $|L|$ 条互不相交的边，即一个基数为 $|L|$ 的匹配。

为证明任何割的容量都至少为 $|L|$：设 $S_1$ 为割中包含源点的一侧，$S_2$ 为割中包含汇点的一侧。考察 $L \cap S_1$：

• 源点到每个 $L \cap (S_1)^c$ 中的顶点都有一条边，这些边跨越割，贡献 $|L| - |L \cap S_1|$ 条；
• $R \cap S_1$ 中每个顶点到汇点都有边被割断，贡献 $|R \cap S_1|$ 条；
• 还需证明从 $L \cap S_1$ 到 $R \cap S_2$ 至少需要 $|L \cap S_1| - |R \cap S_1|$ 条边跨越割。

关键事实：考虑 $L \cap S_1$ 在 $R$ 中的全体邻居，其数量必须不少于 $|L \cap S_1|$。否则，把从 $L \cap S_1$ 出发到 $R$ 的度数之和（$d |L \cap S_1|$）按两侧分别累加，会推出 $R$ 中某些顶点的度数高于 $d$，与 $d$-正则性矛盾。因此 $L \cap S_1$ 的邻居总数 $\ge |L \cap S_1|$；其中位于 $S_1$ 内的邻居至多 $|R \cap S_1|$ 个，故位于 $S_2$ 内的邻居数至少为 $|L \cap S_1| - |R \cap S_1|$。每个这样的邻居都贡献一条跨越割的边。

三类跨越割的边数相加：

$$(|L| - |L \cap S_1|) + (|L \cap S_1| - |R \cap S_1|) + |R \cap S_1| = |L|.$$

由于每条边容量为 1，任何割的容量至少为 $|L|$。证毕。

推理链回顾：$d$-正则 $\Rightarrow$ 任意 $L$ 子集邻域大小不小于该子集大小（度数计数论证）$\Rightarrow$ 最小割容量 $\ge |L|$ $\Rightarrow$ 最大流值 $\ge |L|$（最大流-最小割定理）$\Rightarrow$ 整数性保证取到 $|L|$ 条不相交匹配边 $\Rightarrow$ 基数为 $|L|$ 的匹配存在。注意该结论与 26.3-4 的 Hall 定理是自洽的：$d$-正则图的邻域条件恰好满足 Hall 条件，因此 $|L| = |R|$ 时完美匹配存在。

延伸：26.3 的结论在 CLRS 仓库中的复用与佐证

26.3 小节的"匹配 = 流"化归不仅是本节的习题素材，其结论在仓库第 26 章其他小节与章末问题中被反复调用，可作为理解本节价值的交叉证据：

• Problems/26-2.md（最小路径覆盖）：把有向无环图的最小路径覆盖构造为二分匹配问题，并直接引用 26.3 节的结论，称"我们可以用 $O(VE)$ 时间求最大流"——这是 $O(VE)$ 复杂度声明的仓库内直接证据。
• Problems/26-6.md（Hopcroft-Karp 算法）：定义匹配语境下的增广路径（在 $L$ 中未匹配顶点与 $R$ 中未匹配顶点之间、边在 $M$ 与 $E - M$ 间交替的简单路径），并用对称差 $M \oplus P$ 论证每次增广使匹配基数加 1——其 a、b 部分的证明方法与 26.3-4 中"沿残量边交替回溯"的论证一脉相承，最终得到 $O(\sqrt V E)$ 的更快算法。
• 26.4-5（push-relabel 求二分图最大匹配）：直接承接"按上一小节构造二分图的流网络"，说明预处理阶段先对 $L$ 中所有顶点重标记、再从每个 $L$ 顶点向 $R$ 推送，给出 $O(V(E + V))$ 的分析。
• Problems/26-1.md（逃生问题）：把网格上的顶点不相交路径问题建模为带顶点容量的流网络（等价于 26.1-7 的"拆点"归约），其"所有边容量为 1、增广路径即单位流、最大流等于 $m$ 当且仅当可逃生"的论证，与 26.3 节的单位容量化归完全同构。
• Problems/26-3.md（算法咨询公司）与Problems/26-4.md（增量更新最大流）：分别在"有限容量割 + 无穷容量边"与"容量增减 1 后的单次 Ford-Fulkerson 迭代"中再次使用整数性与单次增广 = 流值 +1 的性质。

仓库中本节及第 26 章全部内容以 Markdown + KaTeX 组织（参见 README.md 的站点说明与 mkdocs.yml 中26.3 Maximum bipartite matching: Chap26/26.3.md的导航配置），各小节标题、定理编号与教材一致，方便按题号 26.3-1 至 26.3-5 直接检索对照。若需要动手验证，可按 README.md 中的说明使用 MkDocs 本地构建站点，或直接在浏览器中逐题阅读；仓库仅用于查看与学习，不涉及对仓库本身的修改。

• 文档
• 教程
• 教育