CSCI3160 L16 最大流、残量网络与最小割

课程：CSCI3160 Design and Analysis of Algorithms 本讲：L16 最大流、残量网络与最小割 · 原件 L16-Graph-06-Max-Flow-未核-隐藏.pdf（本地课件） p.1–25 定位：把容量约束、可撤销的增广和最优性证书连起来。

p.1–3：容量是上限，流量是选择【新】

p.1 为标题。2026-09-17 留存的官网课件行标注此主题不纳入考试；以下保留完整学习内容，不能据此推断其他学期试卷范围。p.2 输入无孤立点的有向简单图，源 s 没有入边、汇 t 没有出边。p.3 容量是非负整数，不存在的有向边容量0。

图（p.3）：s、t 与 v1–v4 的网络。元素：s 出边容量16、13，t 入边容量20、4；内部也有反方向边。看什么：两个方向是两条独立容量约束，不能把图视为无向管道。

原图完整容量及 p.4–5 的流量如下。未列出的有向边容量、普通流量都为 0。

有向边	容量 c	普通流 f
s→v1	16	11
s→v2	13	8
v1→v2	10	0
v2→v1	4	1
v1→v3	12	12
v3→v2	9	4
v2→v4	14	11
v4→v3	7	7
v3→t	20	15
v4→t	4	4

p.4–6：每个中间点都要守恒

p.4 $f(u,v)\le c(u,v)$

流量非负且不超过容量；除源汇以外，每点流入和等于流出和。p.4–5 边标 x/y 表示流量/容量。示例源流出11+8=19，汇流入15+4=19；v1 流入11+1=12、流出12；v2 流入8+4=12、流出1+11=12。

p.6 宣称画出值23的最大流，但图中 v3→v2 仍标4/9：v2 流入12+4=16、流出1+11=12，违反守恒；v3 也不守恒。按其他数值不变，应将该边流量改为0才能构成可行流。这是原图数值不一致，不能把图照抄成合法答案。后文 p.16 给出了另一组合法的23流。

p.7–9：对流可以抵消

p.7 源流出等于汇流入：把所有中间点的守恒等式相加，内部边一进一出抵消即可。p.8 clean flow 要求同一对点不能双向都有正流。图中 v1→v2 为1、反向为2，同时减去1后变为0和1，净流量不变、容量仍满足，源汇值也不变。p.9 因此限制只考虑 clean flow 不会降低最大流值。

p.10–12：净流量允许负数

p.10 $F(u,v)=-F(v,u)$

general flow 用反对称 F 记录净流：由 clean f 得 $F(u,v)=f(u,v)-f(v,u)$ ；反过来 $f(u,v)=\max(F(u,v),0)$ 。p.11 的两个图就是这组一一对应。负数表示反向净流，并不表示普通 f 可以是负数。

完整的净流约束是：对所有有序点对有 $F(u,v)\le c(u,v)$ 和 $F(u,v)=-F(v,u)$ ；对内部点 u 有 $\sum_{v\in V}F(u,v)=0$ 。源点净流值为 $\lvert F\rvert=\sum_vF(s,v)$ 。原页把可含负数的数域记为 N，本文明确按整数理解，以免把负净流误排除。

由 clean f 构造 F 时，每对至少一边流量为 0，故取正部能恢复原来的 f。反向从 F 取正部，若 F(u,v)>0，则由反对称性另一方向非正，所以所得 f 自动 clean；又 $f(u,v)-f(v,u)=F(u,v)$ ，守恒和流值随之保留。这说明求两种表示下的最大值等价。

p.12 残量 $R(u,v)=c(u,v)-F(u,v)$ ，大于0才在残量图放边。例如净流 F(v1,v2)=−1，原容量10，故该方向残量11：其中1用于撤销既有反向流，剩余10才是新送正向流。

p.13–15：增广能撤销早先的安排

图（p.13–14）：从值19的净流得到残量图，红色增广路径 s→v1→v2→v3→t。元素：残量依次5、11、4、5，瓶颈为4。看什么：v2→v3 在原图容量为0，却因已有 v3→v2 流4而成为残量边；沿它增广是在撤销反向流。

p.13 残量的全部正值列在下表；每行是一对相反方向，0 表示该方向不进入残量图。

点对，按左→右顺序	正向残量	反向残量
s,v1	5	11
s,v2	5	8
v1,v2	11	3
v1,v3	0	12
v2,v3	4	5
v2,v4	3	11
v3,v4	7	0
v3,t	5	15
v4,t	0	4

例如 v2→v1 原容量 4、净流 1，余量是 3；v3→v4 原容量 0、净流 −7，余量为 7。

p.14 用 BFS 或 DFS 搜残量图的 s–t 简单路径。p.15 沿路径方向给 F 加瓶颈，反方向减同一瓶颈。内部点一入一出，守恒保留；瓶颈保证容量不破；反对称性由成对更新保持；源流出恰增加4。

p.16–17：实际把19改成23

图（p.16）：增广前、红路径、增广后三层图。元素：s→v1 从11变15；F(v1,v2) 从−1变3；F(v2,v3) 从−4变0；v3→t 从15变19；源另一条边仍8。看什么：对应 clean flow 的 v1→v2 为3、v2→v1 为0，v3→v2 也为0。v1 流入15=12+3，v2 流入8+3=11，v3 流入12+7=19，均守恒。

p.17 Ford–Fulkerson 从零流起，反复构造残量图并增广，直到没有增广路。必须搜索残量图；只找原图上“还没满”的正向边不能撤销错误安排。

可直接执行的净流版本：

所有 F(u,v)=0
循环：
  对有正残量 c(u,v)-F(u,v) 的方向建立残量边
  搜索 s 到 t 的简单路径 P
  若找不到：返回 F 及从 s 可达的集合 S
  delta = P 上的最小残量
  对 P 上每条 (u,v)：
    F(u,v) += delta
    F(v,u) -= delta

补充：最小例子看懂“撤销”而不把它当逆向运输。 自取每条边容量均为 1 的网络：s→a、s→b、a→b、a→t、b→t。若第一次贪心选 s→a→b→t，得到流值 1，看原图正向剩余容量似乎再也送不了。但残量图有 s→b→a→t，其中 b→a 用来撤销 a→b 上的 1。增广后，a→b 的流变 0，s→a→t 与 s→b→t 各送 1，总流值 2。

边	第一次增广后	撤销增广后
s→a	1	1
s→b	0	1
a→b	1	0
a→t	0	1
b→t	1	1

a、b 的流入始终等于流出，容量始终未超。反向残量不是新增一条物理管道，而是修改旧方案的合法余地。

自测：总流量等于某个割容量前，还需要检查什么？

先确认当前流可行：每条边在容量内，中间点守恒。一个违反守恒的数字标注即使在源点相加得到 23，也不是可与割上界配对的可行下界。正文 p.6 的原图错误正说明“总数看着对”不能代替局部约束核对。

p.18–20：割给任何流一个上界

p.18 把 V 分为 S、T，s 在 S、t 在 T。对 S 中各点求净流守恒，内部边抵消，得到流值等于从 S 到 T 的净流和。p.19 每条净流不超过容量，所以流值不超过割容量。这里割容量只加从 S 到 T 的有向容量，不加反方向。

把割恒等式明确写出：

|F|=\sum_{u\in S}\sum_{v\in V}F(u,v) =\sum_{u\in S,v\in T}F(u,v) \le\sum_{u\in S,v\in T}c(u,v)=c[S,T].

第一步中 S 内除 s 外全是守恒点，第二步因 S 内两个相反方向相消；不等式才使用容量约束。无增广路时跨割残量全为 0，不等式逐项变成等式，故当前流和此割同时最优。

p.20 “The Max-Flow Min-Cut Theorem”

p.20 三个等价陈述：流最大；残量图无增广路径；存在容量等于当前流值的割。例中取 S={s,v1,v2,v4}、T={v3,t}，跨割容量12+7+4=23，所以前面构造的23流已经最优。

p.21–23：无增广路如何给出证书

p.21 最大流若还有增广路就能变更大，矛盾；若流值等于某割容量，则任何流都不能超过它。p.22 剩下关键方向：取 S 为残量图中从 s 可达的点，T 为其他点。没有增广路意味着 t 在 T；若 S→T 有正残量，T 的终点也会可达，矛盾。因此所有跨割边残量0，即 F 等于 c。p.23 求和便得流值等于割容量。

p.22 原式写“S can reach v”应读作小写源点 s 能到 v；p.19 的 c[S,t] 也是上下文中的 c[S,T]。这些记号修正不改变定理。

p.24–25：容量整数与运行时间

p.24 从整数零流出发，每次瓶颈为正整数，流值至少加1，所以至多 M 次成功增广，再加一次失败搜索。搜索时间 $O(E)$ ，总界更完整写为 $O(E(M+1))$ ，当 M≥1 常简写 $O(EM)$ 。这是依赖容量数值的伪多项式界，不是关于输入位数的强多项式界。

p.25 若每次 BFS 找边数最少增广路，可得 Edmonds–Karp 的 $O(VE^2)$ ；讲义明确说证明细节不要求。本讲不把任意 DFS 增广也标成该时间界。

本讲核心考点

（B 级：2026-09-17 留存的教师官网课件行）最大流标注为非考试内容；该标注只对应所核网页。
（C 级通识）容量、守恒、净流和残量的区别。
（C 级通识）用反向残量边解释撤销，并证明增广保持可行。
（C 级通识）从无增广路提取等值割，证明最优。

附录

本讲所需过程已在正文展开。

来源与证据

本次逐页复核：2026-10-13，依据上述本地课件；保留已发布深化内容，页码指 PDF 物理页。历史考试演练保留其原有出处，本次不将旧记录冒充重新阅卷。
原件：L16-Graph-06-Max-Flow-未核-隐藏.pdf（本地课件）；页码均为 PDF 页号。
版本记录（2026-09-17）：当时从教师官网下载并逐字节核对，与本地原件一致；此日期不是本次重新联网核验。原始学期未核，不据网页学期补猜。
发布状态（2026-09-17 核验时）：官网链接所在行隐藏，当时按预习参考处理；不据此推断后续发布或考试范围。
既有考试证据记录（2026-09-17）：当时读取了教师官网、Midterm-2021T1-题目.pdf、Midterm-2021T1-题解.pdf、Review-Quiz-2020T2-题目.pdf、Review-Quiz-2020T2-题解.pdf、Quiz-01-2025T1-题解.pdf、Midterm-A-2025T1-缺题干-解答.pdf、Quiz-02-2025T1-缺题干-解答.pdf、Quiz-03-2025T1-缺题干-解答.pdf、Final-2021T1-题解.pdf、Final-2024T1-缺判断-题目.pdf、Final-2025T1-题目.pdf、Final-2025T1-缺题干-解答.pdf；未识别用途的 PDF：无
缺题干解答卷仅用于核对已取得的题面，不由答案反推题目。