如何证明流网络中最小割的并集和交集也是一个最小割
How to show that union and intersection of min cuts in flow network is also a min cut
这个证明到处都被跳过了，据说是 Min-Cut-Max-Flow 定理的推论......通常是这样的：
设 S1 和 S2 为流网络的最小割。那么S1∪S1和S1∩S2也是最小割。
谁能告诉我这是怎么证明的？
根据 min-cut-max-flow 定理，对于每个最大流和每个切割，当且仅当所有穿过它的弧都饱和时，该切割是最小的（这是互补松弛的类比，可通过观察证明穿过切口的总流量是总流量）。给定最小割 S1 和 S2，每条穿过 S1 ∪ S2 的弧都穿过 S1 或穿过 S2，因此每条这样的弧都是饱和的。 S1 ∩ S2 同上。
这个证明到处都被跳过了，据说是 Min-Cut-Max-Flow 定理的推论......通常是这样的：
设 S1 和 S2 为流网络的最小割。那么S1∪S1和S1∩S2也是最小割。
谁能告诉我这是怎么证明的？
根据 min-cut-max-flow 定理，对于每个最大流和每个切割，当且仅当所有穿过它的弧都饱和时，该切割是最小的（这是互补松弛的类比，可通过观察证明穿过切口的总流量是总流量）。给定最小割 S1 和 S2，每条穿过 S1 ∪ S2 的弧都穿过 S1 或穿过 S2，因此每条这样的弧都是饱和的。 S1 ∩ S2 同上。