云南好家佳清洁设备深耕清洁行业近20年一站式采购服务商
2026/9/30 9:55:06
就在接下来的第 27 页到第 35 页，核心是最大流最小割定理。它证明了你问的“为什么没有增广路径时，流就是最大流”。
核心逻辑一句话：没有增广路径 ⇒ 残量网络中 s 到 t 不可达 ⇒ 可以定义一个割，其容量恰好等于当前流值 ⇒ 由弱对偶性（流值 ≤ 任何割容量），当前流值 = 割容量，因此是最大流。
第 27 页：流与割的关系（净流）
内容：
定义：割 (A, B) 的净流 = 从 A 到 B 的边的流量之和 减去 从 B 到 A 的边的流量之和。（见上图，一个很好的例子。A是黑点set，B是白点set。）
流值引理：任意流 f 和任意割 (A, B)，净流 across (A, B) = 流的值。
示例：净流 = 5 + 10 + 10 = 25，流的值 = 25。
物理含义：
净流是“净通过量”，正向减去反向。
引理说明：无论你怎么切，从 A 到 B 的净流量总是等于整个系统从 s 到 t 的流量值。
物理原因：中间顶点守恒，流量不会在 A 内部消失或产生。所以所有从 s 出发的流量最终都必须穿过割。
注意这里的cut是st cut，也就是s在一个set，target在一个set的cut。
第 28 页：净流示例（另一个割）
内容：另一个割的净流 = 10 + 5 + 10 = 25，流的值 = 25。
物理含义：同一流，不同割，净流相同。验证流值引理。
第 29 页：净流示例（含反向边）
内容：净流 = (10+10+5+10+0+0) - (5+5+0+0) = 25。
物理含义：明确展示正向边和反向边的流量如何计算净流。
第 30 页：流值引理证明
内容：证明：对 B 的大小归纳。
基础：B = {t}，净流 = t 的流入 = 流的值。
归纳步骤：将任意顶点从 A 移到 B，由于局部平衡，净流不变。
物理含义：
从 B 只有 t 开始，逐渐把顶点从 A 移到 B，净流始终等于流的值。
这是因为移动一个顶点时，它的流入 = 流出，所以净流不变。
第 31 页：弱对偶性
内容：
弱对偶：任意流的值 ≤ 任意割的容量。
证明：流的值 = 净流 across 割 ≤ 割的容量（因为净流 ≤ 正向边容量之和 = 割容量）。
物理含义：
这是 maxflow-mincut 定理的一半：最大流的值 ≤ 最小割的容量。
物理直觉：任何流都必须穿过任何割，所以流的值不可能超过割的容量。
第 32-34 页：最大流最小割定理
内容：
增广路径定理：流 f 是最大流 当且仅当 没有增广路径。
最大流最小割定理：最大流的值 = 最小割的容量。
证明三个条件等价：
i. 存在一个割的容量等于流 f 的值。
ii. f 是最大流。
iii. 没有增广路径。
[i ⇒ ii]：如果割容量 = 流值，那么任何流的值 ≤ 割容量 = 流值，所以 f 是最大流。
[ii ⇒ iii]：逆否命题：如果有增广路径，则可以改进流，所以 f 不是最大流。
[iii ⇒ i]：如果没有增广路径，定义 A 为从 s 沿残量网络可达的顶点集合，B 为其余。则割 (A, B) 的容量 = 净流 = 流的值。
物理含义：
这是整个最大流理论的核心。
当没有增广路径时，残量网络中 s 不能到达 t。此时，从 s 可达的顶点集合 A 和其余顶点 B 构成一个割。所有从 A 到 B 的边都是满的（否则会有残量容量，B 中的顶点会从 A 可达），所有从 B 到 A 的边都是空的（否则反向残量容量会让 B 中的顶点可达）。所以割的容量 = 净流 = 流的值。
因此，流的值 = 割的容量，达到了弱对偶的上界，所以是最大流，也是最小割。
第 35 页：从最大流计算最小割
内容：
通过增广路径定理，没有增广路径。
计算 A = 从 s 沿残量网络可达的顶点集合（无满正向边或空反向边）。
图中阴影部分 A，其余 B。割的容量 = 28。
物理含义：
算法终止后，从 s 出发在残量网络中做一次 BFS/DFS，标记所有可达顶点，这些顶点构成 A，其余为 B。
这个割就是最小割。
一、最大流和最小割的定义
Q：什么是最大流，什么是最小割？什么又是最大流等于最小割？既然说等于，那么二者是相同的单位，应该是说图的最大流等于最小割下的流。那么什么是割的流？那就是刚才讲到的net flow对吗？当我们做完st cut得到两个set，在set之间的net flow就是割的流？那么，当我们得到一个最大流，它肯定等于割的流，可是只要是st cut，cut的net flow都将是流的值。这么一看，似乎又不是如此了。
A：你把两个不同的量混在一起了：
割的容量（capacity）：固定的数。只算从 A 到 B 的边的容量之和，不算反向边。
割的净流（net flow）：当前流分配下的实际通过量。从 A 到 B 的流量之和 减去 从 B 到 A 的流量之和。
1.流的值引理
对于任意割 (A, B)，当前流 f 的净流 across (A, B) 都等于流 f 的值。
也就是说，不管你怎么切，净流都相同，都等于从 s 到 t 的总流量。
2. 弱对偶性
对于任意割 (A, B)：
流的值 = 净流 across (A, B) ≤ 割的容量。
为什么净流 ≤ 割容量？因为净流 = 正向流量 - 反向流量 ≤ 正向流量 ≤正向容量之和 = 割容量。
所以：任何流的值 ≤ 任何割的容量。
3. 最大流最小割定理
最大流：所有可行流中，流的值最大的那个。
最小割：所有st 割中，割的容量最小的那个。
定理：最大流的值 = 最小割的容量。
注意：是“最大流的值”等于“最小割的容量”，不是“最大流等于割的净流”。
4. 为什么最大流等于最小割容量？
当流达到最大时，没有增广路径。此时，从 s 在残量网络中可达的顶点集合 A 和其余 B 构成一个割。这个割满足：
所有从 A 到 B 的边都是满的（flow = capacity）。
所有从 B 到 A 的边都是空的（flow = 0）。
因此，对于这个割：
净流 = 正向流量之和 - 反向流量之和 = 正向容量之和 - 0 = 割的容量。
而净流又等于流的值，所以：
流的值 = 割的容量。
由于任何流的值 ≤ 任何割的容量，这个割的容量已经达到了上界，所以这个流是最大流，这个割是最小割。
5. 回答你的疑问
“当我们得到一个最大流，它肯定等于割的流，可是只要是 st cut，cut 的 net flow 都将是流的值。”
对。对于任意割，净流都等于当前流的值。所以当你得到最大流时，任意割的净流都等于最大流的值。
但割的容量不一定等于最大流的值。只有最小割的容量才恰好等于最大流的值。其他割的容量可能更大。
所以“最大流 = 最小割”指的是：最大流的值 = 最小割的容量。
不是“最大流等于割的净流”。净流永远等于流的值，但容量是固定的上界。当流最大时，存在一个割，其容量恰好等于流值，这个割就是最小割。
二、三个条件等价（p32~34）
Q：好吧，我觉得这里我看不懂的原因是偷了点懒，我们得重新看第27页的lemma： Let f be any flow and let (A, B) be any cut. Then, the net flow across (A, B) equals the value of f.
这一句，我没太看懂。我知道什么是net flow，但是为什么f可以是任意flow？这里的flow是什么？是整张图最终的流值吗，还是任选几条边的流值，还是(A,B)的流值？
A：你的困惑在于把“流（flow）”和“流的值（value of flow）”混在一起了。我们拆开。
1. 什么是“流 f”？
流 f 不是“几条边的流量”，也不是“整个图的流值”。它是一个完整的分配方案：给图中每条边都指定一个流量值，满足两个约束：
容量约束：每条边的 flow 在 0 和 capacity 之间。
局部平衡：除 s 和 t 外，每个顶点的流入 = 流出。
所以，一个“流 f”就是一张表，记录了每条边当前的流量。
2. 什么是“流的值”？
流的值 = 从 s 流出的净流量 = 流入 t 的净流量。
它是一个数字，描述整个流 f 的总量。
对于一个给定的流分配方案 f，它的值是一个固定的数字。
解读：流是一种分配方案，对于路径分配具体的流值，导致了特定的t流入值/s流出值，因此流值就是s的流出值，t的流入值。
3. 流值引理在说什么？
引理：对于任意流 f 和任意割 (A, B)，穿过这个割的净流等于流 f 的值。
（本质上是说，s在一边，t在一边，这样形成的割，不会有超越s出t如的流值，即st cut本质上是一种s->t的等效。这个引理的意义在于，把流和割联系起来了，使我们能联系局部的分割和整图的流。）
注意：
流 f 是任意的：只要满足容量约束和局部平衡，不管你怎么分配，不管你怎么选割。
净流 across (A, B) = 从 A 到 B 的流量之和 - 从 B 到 A 的流量之和。
引理说的是：这个固定的数字f的值，等于穿过任意割的净流。
4. 为什么这是对的？（物理直觉）
想象你把 A 里面所有顶点的“流出 - 流入”加起来。
对于 A 内部的边：它连接 A 中的两个顶点，对其中一个贡献流出，对另一个贡献流入。加总时，这两项抵消。
对于从 A 到 B 的边：它从 A 中的顶点流出，贡献 +flow。
对于从 B 到 A 的边：它从 B 流入 A，对 A 中的顶点来说贡献 -flow。
所以，A 中所有顶点的“流出 - 流入”之和 = 净流 across (A, B)。
但根据局部平衡，A 中除 s 外的每个顶点的“流出 - 流入”都等于 0。所以只剩下 s 的贡献。
s 的“流出 - 流入” = 流的值（因为 s 是源点，它的净流出就是整个流的值）。
因此：净流 across (A, B) = 流 f 的值。
5. 回答你的具体问题
“f 可以是任意 flow，这里的 flow 是什么？”
f 是一个完整的流量分配方案（每条边都有流量值，满足约束）。
“是整张图最终的流值吗？”
不是。流 f 是一张表，流的值是一个数字。引理说：这张表穿过任意割的净流，等于这张表的总值。
“还是任选几条边的流值？”
不是几条边。它是所有边的流量分配。
“还是 (A, B) 的流值？”
(A, B) 的净流是引理左边的东西。引理说它等于流 f 的值。
6. 为什么这对最大流最小割定理重要？
因为弱对偶性（第 31 页）用到了这个引理：
流的值 = 净流 across (A, B) ≤ 割的容量。
左边是流的值，右边是割的容量。净流 ≤ 割容量是因为净流 = 正向流量 - 反向流量 ≤ 正向流量 ≤ 正向容量之和 = 割容量。
所以，任何流的值 ≤ 任何割的容量。这就是弱对偶性，也是 maxflow-mincut 定理的一半。
Q：也就是说我们目前还未证明增广路径为什么能得到最大流，而是直接就着这个往后推了，所以我们可以理解流等于割，但不能理解按照最大流就可以得到没有B到A，只有A到B的割，因为我们还没通过证明理解增广到没有B到A就是最大流。然后，我们推完了前面，才在32~34页回过头来看这一点？
A：基本正确，但可以再精细一点。
顺序确实是这样的
第 27-31 页先建立了一般性的工具：
流值引理（第 27 页）：对任意流 f 和任意割 (A,B)，流的值 = 净流（小于割的容量）。
弱对偶性（第 31 页）：对任意流和任意割，流的值 ≤ 割的容量。
这两个结论不依赖增广路径，也不依赖最大流。它们是在“所有可能的流”和“所有可能的割”上普遍成立的。
然后第 32-34 页才回过头来处理增广路径定理和最大流最小割定理。
需要精确化的一点：你说“可以理解流等于割”
更准确地说，在第 27-31 页你能理解的是：
净流 across 割 = 流的值（流值引理）。
流的值 ≤ 割的容量（弱对偶性）。
（注意这里有流、流的值、割、割的净流、割的容量，这些东西。要注意区分。）
你尚不能理解的是：为什么“没有增广路径”意味着“存在一个割，其容量恰好等于流的值”。这正是第 34 页 [iii ⇒ i] 要证明的。
所以“流等于割”这个说法不准确。准确的说法是：流的值 ≤ 割的容量（弱对偶性），而最大流最小割定理说的是存在一个流和一个割，使得这个不等式取等号。
第 34 页 [iii ⇒ i] 在证明什么？
它构造了一个特定的割：
A = 在残量网络中从 s 可达的顶点。
B = 其余顶点。
然后证明这个割满足：
所有从 A 到 B 的边都是满的（flow = capacity）。
所有从 B 到 A 的边都是空的（flow = 0）。
于是：
割的容量 = 正向容量之和 = 正向流量之和 = 净流 = 流的值。
最后一步用了流值引理。而“净流 = 流的值”这个等式来自第 27 页。所以第 32-34 页的证明确实依赖了前面建立的引理。
总结
第 27-31 页：建立一般性工具（流值引理、弱对偶性）。
第 32-34 页：用这些工具证明增广路径定理和最大流最小割定理。
你之前“不能理解按照最大流就可以得到没有 B 到 A 的割”，正是因为那部分证明在第 34 页才出现。现在你已经看到了。
Q：第32~34页，这里的解释没太看懂，再教教我吧。
证明三个条件等价：
i. 存在一个割的容量等于流 f 的值。
ii. f 是最大流。
iii. 没有增广路径。
[i ⇒ ii]：如果割容量 = 流值（这是i里面提供的条件），那么任何流的值 ≤ 割容量 = 流值（这是推导出来的吗？那么应该还要分步写：并且因为任何流的值小于等于割容量，又注：割容量是可以大于bottleneck容量的；那么：任何流的值 ≤ 割容量 = 某个流值），所以 f 是最大流（是啊，这怎么会被推出来呢）。
（这里的概念问题，已经在上面解决。）
[ii ⇒ iii]：逆否命题：如果有增广路径，则可以改进流，所以 f 不是最大流。
[iii ⇒ i]：如果没有增广路径，定义 A 为从 s 沿残量网络可达的顶点集合，B 为其余。则割 (A, B) 的容量 = 净流 = 流的值。（更搞不懂，不如先把i->ii讲清楚）
A：案就藏在第 31 页已经证明的弱对偶性里。
先回顾弱对偶性（第 31 页）
弱对偶性说的是：任意流的值 ≤ 任意割的容量。
这是对所有流和所有割都成立的。
物理直觉：任何流都必须穿过任何割，所以流的值不可能超过割的容量。
现在看 i ⇒ ii
条件 i 说：存在一个割 (A, B)，使得割的容量 = 流 f 的值。
设这个割的容量为 C，流 f 的值为 V。条件 i 告诉我们：C = V。
现在取任意另一个流 f'，它的值为 V'。
根据弱对偶性：V' ≤ C（因为 f' 是任意流，C 是任意割的容量）。
但 C = V，所以 V' ≤ V。
这意味着：没有任何流的值能超过 V。所以 f 就是最大流。这就证明了 ii。
你之前的困惑
你说：“任何流的值 ≤ 割容量 = 某个流值，所以 f 是最大流，这怎么会被推出来呢？”
拆开看：
任何流的值 ≤ 割容量：这是弱对偶性，对所有流和所有割都成立。
割容量 = 某个流值：这是条件 i 给的。
所以任何流的值 ≤ 这个流值：把 2 代入 1 得到。
任何流的值都不超过这个流值，意味着这个流值就是最大值。
这不是循环论证，而是用“弱对偶性”这个已经证明的定理，把“存在一个割容量等于流值”转化成了“这个流值就是上界”。
再看 iii ⇒ i（如果你还想往下）
如果 iii 成立（没有增广路径），我们构造一个割：
A = 在残量网络中从 s 可达的所有顶点。
B = 其余顶点。
因为 s 在 A 中，且没有增广路径意味着 t 不在 A 中（t 从 s 不可达），所以 (A, B) 是一个合法的 st-割。
现在看这个割的容量：
对于任意从 A 到 B 的边 e：它的 flow 必须等于 capacity。因为如果 flow < capacity，那么残量网络中就会有一条从 A 到 B 的正向边，B 中的顶点就会从 s 可达，矛盾。
对于任意从 B 到 A 的边 e：它的 flow 必须等于 0。因为如果 flow > 0，那么残量网络中就会有一条从 A 到 B 的反向边，B 中的顶点就会从 s 可达，矛盾。
所以这个割的净流 = 从 A 到 B 的流量之和 - 从 B 到 A 的流量之和 = 从 A 到 B 的容量之和 - 0 = 割的容量。
而根据流值引理（第 27 页），净流 = 流 f 的值。
所以割的容量 = 流 f 的值。这就证明了 i。
总结三个条件的关系
i ⇒ ii：用弱对偶性，任何流 ≤ 任何割容量。如果有一个割容量 = 流值，那这个流就是最大的。
ii ⇒ iii：逆否命题。如果有增广路径，就能改进流，所以不是最大流。
iii ⇒ i：没有增广路径时，构造割 (A, B)，证明其容量恰好等于流值。
三个条件等价，所以：
最大流（ii）当且仅当没有增广路径（iii）当且仅当存在割容量等于流值（i）。
因此，最大流的值 = 最小割的容量。