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

Question

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

设 S1 和 S2 是流网络的最小割量。那么 S1?S1 和 S1?S2 也是最小切割。

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

Answer 1

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