找到流量网络的所有MIN切割的联合

Question

我正在尝试解决以下问题：

给定流量网络 $ n=（g=（v，e），c，s，t）$ 。让 $ \ mathcal f $ 是所有最小剪切的集。证明 $ \ mathcal f $ 在交叉点和工会下关闭，即每个 $ s_1，s_2 \ In \ mathcal f ，s_1 \ cup s_2 \ in \ mathcal f $ 和 $ s_1 \ cap s_2 \ in \ mathcal f $ 。

我使用最小切割最大流定理照顾好的正好。

另一部分是我遇到麻烦的部分：

给定max flow $ f $ ，查找 $ s _ {\ min}=bigcap_ {s \ in \ mathcal f} s \ text {和} s _ {\ max}=bigcup_ {s \ in \ mathcal f} s $ 。

我意识到，当考虑min切割 $（s，t）$ ，并且给定残差图（可以从给定的最大流量构建），从 $ s $ （源节点）中，每个可到达的顶点必须是 $ s $ ，所以我能够使用它来提出算法来查找 $ s _ {\ min} $ 。

但是为了找到 $ s _ {\ max} $ 的算法，我有点难以让我的手指放在一个min切割边缘的财产上，即是一个切割边缘（或者顶点在 $ s $ ）所花费的是什么？

我不是在寻找完整的答案，而是暗示..任何帮助都受到赞赏。

Answer 1

note $ s _ {\ max}= v- \ bigcap_ {s \ in \ mathcal {f}}（v-s）$ 。 $ \ bigcap_ {s \ in \ mathcal {f}}（vs）$ 是的所有顶点的集合$ t $ 在残余图中可以访问。

$ \ bigcap_ {s \ in \ mathcal {f}}（vs）$ 是 $ T $ 在剩余图表中可以访问与 $ s _ {\ min} $ 的原因相同从 $ s $ 可到达的所有顶点。您可以使用互补松弛条件来证明这一点。