algorithm - 如何证明流网络中最小割的并集和交集也是最小割

Question

这个证明到处都被跳过了，据说是 Min-Cut-Max-Flow 定理的推论......它通常是这样的：

令 S1 和 S2 为流网络的最小割。那么 S1∪S1 和 S1∩S2 也是最小割。

谁能告诉我这是如何证明的？

Answer 1

根据最小割最大流定理，对于每个最大流和每个割，当且仅当穿过它的所有弧都饱和时，该割是最小的（这是互补松弛的模拟，可通过观察总流来证明穿过切口是整体流程）。给定 min 割 S1 和 S2，穿过 S1 ∪ S2 的每条弧都穿过 S1 或穿过 S2，所以每条这样的弧都是饱和的。S1 ∩ S2 同上。