本页目录
图论与组合 III · 匹配、网络流与图上的算法
收官页三大块：匹配（Hall 婚配定理——"什么时候人人有对象"）、网络流（最大流最小割——LP 对偶在离散世界的加冕礼，优化 IV 的欠条在此清偿）、以及图上的算法与随机游走（PageRank 与 Markov 链的会师）。图论在此从"结构的描述"升级为"资源的调度"。
先修入口：图的基本理论、线性规划与动态规划、Markov 链。
学习层：一条反向边，为什么能救回全局最优？
1. 先做预测：第一条路走错了，还有没有后悔药？
一个应急配送网络只有四个中转位置。每条有向边上的数字是每小时最多能通过的箱数。以下五条边容量都为 1：\(s\to a,s\to b,a\to b,a\to t,b\to t\)。你已经沿 \(s\to a\to b\to t\) 送出 1 箱，随后看起来所有继续向前的路都被堵住。请先判断：
- 已经送出的那 1 箱是否一定属于某个最大流，还是可能需要把其中一段撤回再改道？
- 残量网络里的反向边代表新建一条反向管道，还是代表取消一部分既有流？
- 找到一个值为 2 的可行流，是否已经证明 2 是最优值？还缺什么证书？
- 容量都是整数时能否找到整数最大流？这个结论能否无条件推广到任意线性规划？
实验先给出完整网络数据，再隐藏计算出的增广路径、流量和割。揭示后可逐次增广，也可直接运行到证书；每一步都把原边流量、正向余量、反向余量和中间点守恒放进同一张账本。
无 JavaScript 时的完整静态读法：考虑边容量全为 1 的网络
若第一次沿 \(s\to a\to b\to t\) 增广 1，当前流值是 1，且 \(a\to b\)、\(b\to t\) 已饱和。残量网络会加入 \(b\to a\)，容量等于已经走过 \(a\to b\) 的流量 1。第二条增广路是
其中 \(b\to a\) 是残量反向边。沿它增广会把原边 \(a\to b\) 的流从 1 减回 0，同时把 \(s\to b\) 与 \(a\to t\) 各加 1。最终
所以流值为 2。此时残量网络中从 \(s\) 出发已无可走的正余量边；可达集是 \(S=\{s\}\)，割边 \(s\to a,s\to b\) 的容量和也是 2。可行流给下界，割给上界；二者相等才构成最优证书。
| 步骤 | 增广路 | 瓶颈 | \(f(a,b)\) | 总流值 | 证书状态 |
|---|---|---|---|---|---|
| 初始 | 无 | -- | 0 | 0 | \(t\) 仍在残量图中可达 |
| 1 | \(s\to a\to b\to t\) | 1 | 1 | 1 | 只有可行流，尚未证明最优 |
| 2 | \(s\to b\to a\to t\) | 1 | 0 | 2 | \(S=\{s\}\)，割容量 \(=2\) |
2. 四本账：容量、守恒、残量与割
对每条原边 \(e=(u,v)\)，可行流满足 \(0\le f_e\le c_e\)；除 \(s,t\) 外，每个顶点满足流入等于流出。残量网络同时记录
这里按每条原边分别建立残量弧；若原图同时有 \(u\to v\) 与 \(v\to u\)，同一方向可能还有来自另一原边的退流余量，须保留两条弧或相加，不能直接遗漏。第一项表示还能继续送多少，第二项表示最多能撤回多少。反向余量不是物理管道，而是修改旧决定的自由度。这也是增广路算法能从局部选择中恢复的原因。
任取 \(s\in S,t\notin S\)，割容量只计算从 \(S\) 指向补集的原始正向边：
反向跨割边不加进这个和。由流守恒，任意可行流值都不超过任意割容量。算法停机时，令 \(S\) 为残量图里从 \(s\) 可达的顶点；若 \(t\) 不可达，则所有从 \(S\) 出去的原边饱和、所有进入 \(S\) 的原边流为零，因而流值恰等于该割容量。
3. 算法边界：最大流最小割不等于“随便走都立刻结束”
- Ford--Fulkerson 是增广框架。 路径选择可以是 DFS，也可以来自别的规则。整数容量时从零流出发，每次的瓶颈和边流保持整数，至少增广 1，因此有限步停机，并存在整数最大流。
- Edmonds--Karp 固定用 BFS。 它每次选择边数最少的增广路，得到 \(O(VE^2)\) 的多项式时间界；这不是任意 DFS 路径规则的复杂度。
- 无理容量需要谨慎。 任意路径版 Ford--Fulkerson 可能不终止，甚至路径选择不当时不收敛到最大值；最大流最小割定理本身仍成立，算法停机论证却不能照搬整数情形。
- 整数性有结构前提。 网络流约束矩阵的特殊结构保证整数容量存在整数最优流；不能据此宣称任意线性规划都有整数最优解。
- “找到大流”不是证明。 只有再给出同值割，或等价地证明残量图中没有 \(s\to t\) 路，才关闭最优性缺口。
4. 从流回到匹配与 Hall 证书
把二部图左侧每点接到源、右侧每点接到汇，并给所有边容量 1。一条整数流路径 \(s\to x\to y\to t\) 就是一对匹配边；容量与守恒保证每个顶点最多用一次。若最大流不能覆盖左侧全部顶点，最小割会暴露一个选择不足的集合，正是 Hall 条件失败的算法证书。于是“匹配、增广路、最小顶点覆盖和网络流”不是四个孤立技巧，而是同一套残量与对偶语言。
5. 迁移问题：瓶颈在哪里，改一单位容量值多少钱？
对实验里的最终最小割任选一条割边，把容量增加 1，再预测最大流是否一定增加 1。随后把一条不在任何当前最小割上的边增加 1，比较结果。先用一张未变化的最小割写上界，再找仍可行的旧流写下界，避免只盯着某一条边。
核对四张割与扩容收益
四点网络只有四种含 \(s\) 而不含 \(t\) 的顶点集。记各边容量为 \(c_{sa},c_{sb},c_{ab},c_{at},c_{bt}\)，对应割容量分别是
全 1 网络的四个值是 \((2,3,2,2)\)，最小割不唯一。把 \(s\to a\) 从 1 扩到 2，源侧割变为 3，但汇侧割仍为 2；旧值 2 的流仍可行，所以最大流仍为 2。桥边 \(a\to b\) 不属于任何最小割，单独扩它也没有收益。只有改变所有仍限制吞吐的割，最大流才可能提高；例如同时把 \(s\to a\) 和 \(a\to t\) 各加 1，就能沿 \(s\to a\to t\) 送 2、沿 \(s\to b\to t\) 送 1，总流达到 3。
若一条边不在任何当前最小割中，扩容后至少保留一张容量不变的最小割，上界不变；旧最优流又给同样下界，故最大流不变。“在某张最小割上”本身不保证正的扩容收益，更不保证任意幅度下线性增长。
1. 二部图匹配与 Hall 定理
匹配：两两不共顶点的边集；完美匹配：覆盖图的全部顶点。只覆盖二部图一侧 \(X\) 的叫 \(X\)-饱和匹配，不一定覆盖 \(Y\)。场景原型：人-岗位、课程-教室、器官捐献配对。
定理（Hall 婚配定理，1935） 二部图 \((X,Y)\) 存在 \(X\)-饱和匹配 \(\iff\) 任何 \(S\subseteq X\) 的邻域满足
（任取 \(k\) 名申请者，他们合起来至少能申请 \(k\) 个岗位；不能有一组人共同挤在更少的选择里。）必要性显然；充分性的经典证法是增广路：未匹配点出发交替走"非匹配边/匹配边"，找到增广路则翻转它使匹配 +1。若还要求完美匹配，必须让匹配也覆盖 \(Y\)；有限二部图中必须有 \(|X|=|Y|\)，此时覆盖 \(X\) 就自动覆盖两侧。这个算法思想同时是匈牙利算法与下节最大流的引擎。
König 定理（二部图）：最大匹配的边数 = 最小顶点覆盖的顶点数——第一对"最大 = 最小"对偶（下节是它的推广），也是 LP 对偶在二部图上恰好整数可解的体现。
2. 网络流：最大流 = 最小割
设定：有向网络，源 \(s\) 汇 \(t\)，边有容量。流：不超容量、中间点守恒；割：取 \(s\in S,t\notin S\)，容量是从 \(S\) 指向 \(\bar S\) 的原始有向边容量和，不把反向跨割边混入。显然任何流值 \(\leq\) 任何割容量（把中间点守恒在 \(S\) 内求和即可——弱对偶，一行）。
定理（最大流最小割，Ford–Fulkerson 1956）
算法即证明：反复找增广路（残量网络中 \(s \to t\) 的正余量路径，含“退流”反向边）提升流量；找不到时，\(s\) 可达集与其余部分形成的割恰好被流填满——该流与该割互证最优。整数容量下任意增广路版会有限步停机；一般实容量要使用有终止保证的实现或独立的极限/LP 论证，不能把任意路径规则的停机当作定理前提。\(\blacksquare\)
三重读法：LP 强对偶的组合化身（标准流 LP 的对偶可取到由 \(s\)-\(t\) 割表示的最优解；整数容量再由网络矩阵结构保证存在整数最优流——优化 IV 的影子价格在此变成“瓶颈边”）；瓶颈定律（系统吞吐由最窄截面决定——供应链、带宽、人力的通用诊断语言）；归约枢纽——二部匹配（Hall/König 是其特例：源连 \(X\)、\(Y\) 连汇、容量全 1）、项目选择、图像分割（视觉里的 graph cut）都化归最大流。
Hall 失败如何读出来：当当前匹配尚未覆盖 \(X\) 时，从所有未匹配的左点出发，交替沿未匹配边向右、沿匹配边向左搜索。若找不到到达未匹配右点的增广路，设到达的左、右点集为 \(Z_X,Z_Y\)。此时 \(N(Z_X)=Z_Y\)，所有到达的右点都被匹配回到达的左点，而至少一个到达的左点未匹配，故 \(|N(Z_X)|=|Z_Y|<|Z_X|\)，直接给出 Hall 反证。这些集合也构成最小顶点覆盖 \((X\setminus Z_X)\cup Z_Y\)。
3. 最短路与图算法速查
| 问题 | 算法 | 思想 | 复杂度级 |
|---|---|---|---|
| 单源最短路（非负权） | Dijkstra | 贪心扩张最近点（贪心正确性=非负权下"最近点不会被绕路改进"） | \(O((V+E)\log V)\) |
| 单源（可负权） | Bellman–Ford | DP 松弛 \(V-1\) 轮（优化 IV Bellman 方程的原产地） | \(O(VE)\) |
| 全对 | Floyd–Warshall | 三重循环 DP（"允许中转点集逐个扩大"） | \(O(V^3)\) |
| 遍历/连通性 | BFS/DFS | 层序/深探（无权最短路 = BFS） | \(O(V+E)\) |
负权不等于负环：Bellman–Ford 还须检查从源可达的负环；若这样的负环能通向目标，目标的有限最短路就不存在。Floyd–Warshall 也需对负环影响的点对作相应标记，不能把松弛表中的有限数当答案。
图着色一嘴：色数 \(\chi(G)\)（相邻异色的最少颜色）；贪心给上界 \(\Delta + 1\)（最大度+1）；判定 \(\chi \leq k\)（\(k\geq3\)）NP-完全。应用原型：排考试（冲突课程异时段）、寄存器分配——"冲突图 + 着色"是资源互斥调度的通用模板。
4. 随机游走与 PageRank（三门课会师）
图上随机游走：每步等概率走向邻居——图上的 Markov 链（无向图可写 \(P = D^{-1}A\)）。至少有一条边的有限连通无向图，其平稳分布唯一且满足 \(\pi_v \propto \deg(v)\)（度大者常驻）；若图二部，链有周期 2，普通迭代会振荡而不从任意初态收敛。加入自环、惰性步或其他非周期机制，才得到通常所说的遍历收敛。对有向图则要分别检查不可约性、周期性和零出度点。
PageRank：网页 = 顶点、链接 = 有向边，重要性 = “随机冲浪者”的平稳分布。采用 \(0\le\alpha<1\) 和均匀跳转。先把零出度网页的行替换为约定的跳转分布，使 \(P\) 真正随机；再以 \(1-\alpha\) 的概率跳转（经典实现常取 \(\alpha\approx0.85\)，但它是设计参数而非定理常数），从而打破死胡同与周期陷阱：
求解 = 幂法迭代（数值线的幂法 + 随机过程的平稳分布 + 本页的图——三门课在一个改变互联网的公式里会师）。对同一行随机矩阵 \(P\) 的两次迭代，\(P^\top\) 作用于列向量时在 \(\ell_1\) 范数下不扩张，所以
因此 \(0\le\alpha<1\) 时，均匀跳转直接给出唯一不动点与收敛界。对于一般有向链，单凭第二特征值不能描述所有有限步误差：非正规性或 Jordan 块还可能带来额外因子；可逆链的谱隙解释要连着相应范数和假设使用。
🔗 现代出口一瞥：常见消息传递式图神经网络（GNN）通过可学习的邻居聚合更新节点表示，其算子可与图上的传播、随机游走比较，但并不都等于随机游走；知识图谱/因果图（Medusa 的因果网正是带类型边的有向图，中心性/连通分量分析直接可用）；谱聚类 = 图 Laplacian 的特征向量（高代谱理论 + 本页）。
5. 典型例题
例 1（Hall 判定） 4 名学生各会做题集 \(\{1,2\}, \{2,3\}, \{1,2\}, \{2\}\)，能否每人分一道不同的题？取 \(S = \{1, 3, 4\}\)（会 \(\{1,2\}, \{1,2\}, \{2\}\)）：\(|N(S)| = 2 < 3\)——Hall 条件破产，无解；且指出了病灶（这三人挤在两道题里）。Hall 定理的价值：不可行时给出"证据"。
例 2（最大流手算） 菱形网络：\(s\to a\)(3), \(s\to b\)(2), \(a\to b\)(1), \(a\to t\)(2), \(b\to t\)(3)。增广 \(s a t\)(2)、\(s b t\)(2)、\(s a b t\)(1)：总流 5；割 \(\{sa, sb\}\) 容量 \(= 5\) 相等 ⇒ 双双最优 ✓。
例 3（PageRank 直觉） 三页环 \(A\to B\to C\to A\) 加一条 \(B\to A\)：无阻尼时求 \(\pi P = \pi\) 得 \(\pi \propto (2, 2, 1)\)（\(C\) 只有一票来源）——链接结构即投票结构。取 \(\alpha=0.85\) 与均匀跳转后，\(\pi\approx(0.3974,0.3878,0.2148)\)：\(A,B\) 仍都高于 \(C\)，但原来的 \(A/B\) 并列被打破，严格排序变为 \(A>B>C\)。\(\blacksquare\)
扩展线收束
五门扩展课与主站的接线图：信息论把"熵/KL/交叉熵"的借条全部收回（概率→AI 的桥）；随机微积分让布朗运动（随机过程）同时流向期权定价（金融）与扩散模型（AI）；时间序列给 Medusa 式预测立了统计军规；图论与组合补齐离散半壁，并让 LP 对偶、Markov 链、幂法在离散世界再就业；博弈论把优化、概率与多智能体决策接起来。至此全站 22 门课，每一页都不是孤岛。