就在接下来的第 27 页到第 35 页核心是最大流最小割定理。它证明了你问的“为什么没有增广路径时流就是最大流”。核心逻辑一句话没有增广路径 ⇒ 残量网络中 s 到 t 不可达 ⇒ 可以定义一个割其容量恰好等于当前流值 ⇒ 由弱对偶性流值 ≤ 任何割容量当前流值 割容量因此是最大流。第 27 页流与割的关系净流内容定义割 (A, B) 的净流 从 A 到 B 的边的流量之和 减去 从 B 到 A 的边的流量之和。见上图一个很好的例子。A是黑点setB是白点set。流值引理任意流 f 和任意割 (A, B)净流 across (A, B) 流的值。示例净流 5 10 10 25流的值 25。物理含义净流是“净通过量”正向减去反向。引理说明无论你怎么切从 A 到 B 的净流量总是等于整个系统从 s 到 t 的流量值。物理原因中间顶点守恒流量不会在 A 内部消失或产生。所以所有从 s 出发的流量最终都必须穿过割。注意这里的cut是st cut也就是s在一个settarget在一个set的cut。第 28 页净流示例另一个割内容另一个割的净流 10 5 10 25流的值 25。物理含义同一流不同割净流相同。验证流值引理。第 29 页净流示例含反向边内容净流 (101051000) - (5500) 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 cutcut的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 cutcut 的 net flow 都将是流的值。”对。对于任意割净流都等于当前流的值。所以当你得到最大流时任意割的净流都等于最大流的值。但割的容量不一定等于最大流的值。只有最小割的容量才恰好等于最大流的值。其他割的容量可能更大。所以“最大流 最小割”指的是最大流的值 最小割的容量。不是“最大流等于割的净流”。净流永远等于流的值但容量是固定的上界。当流最大时存在一个割其容量恰好等于流值这个割就是最小割。二、三个条件等价p32~34Q好吧我觉得这里我看不懂的原因是偷了点懒我们得重新看第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。因此最大流的值 最小割的容量。