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

Question

这个证明到处都被跳过，并被认为是最小割最大流定理的推论......通常是这样的：

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

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

Answer 1

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

Answer 2

当穿过 S 的每条弧都饱和时，割 S 是否总是最小割？