フローネットワークのすべての最小カットの結合を見つける

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 \ \ mathcal f $ 。

その部分私は最小カットマックスフロー定理を使って罰金だけを世話しました。

他の部分は私が問題を抱えていたものです：

最大フロー $ f $ 、find $ s _ {\ min}=bigcap_ {s \ in \ mathcal f} s \ text {および} _ {\ max}=bigcup_ {s \ in \ mathcal f} s $ 。

MINカット $（s、t）$ を考慮して、残差グラフ（与えられた最大フローから構築することができる）を考えると、 $ s $ （ソースノード）から到達可能なすべての頂点は、 $ s $ でなければなりません。 $ s _ {\ min} $ を見つけるためにアルゴリズムを思いつくためにそれを使用することができました。

しかし $ s _ {\ max} $ のアルゴリズムを見つけるために、私はちょっとしたカットエッジの財産に指を置くのに苦労しています。つまり、いくつかの最小カットのカットエッジ（または $ s $ にするための頂点の場合）になるのは何ですか？

私は全回答を探していませんが、むしろヒント。

Answer 1

注 $ 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 $ から到達可能なすべての頂点。あなたは補完的な弛みの状態を使ってこれを証明することができます。