mincut 内の最小の $s$-コンポーネント

Question

有向グラフがあるとします $G=(V,E)$, 、ソース付き $s$ そして沈む $t$, 、そしてそれの最大流量を計算します。そうすれば、最小カットを見つけることができることがわかります $(A,B)$, 、させることで $A$ ソースから到達可能な頂点のセットである $s$.

私の質問はこのセットですか？ $A$ 可能な限り最小の $s$-成分？それはそうですね。正確に言うと、頂点のサブセットは存在しますか? $A^*$, 、 そのような $(A^*, V\setminus A^*)$ は最小カットであり、他のすべての可能な頂点のサブセットに対するものです。 $A$ そのような $(A, V\setminus A)$ はミニカットです。 $size(A^*) \leq size(A)$.

さらに、その他のミニカットについては、 $(C,D)$, 、ありますか $A \サブセット C$?。私もその通りだと思います。しかし、それを証明することはできません。

直感やヒントをいただければ幸いです。

編集

の定義 $s$-成分：最小カットは、頂点の分割です。 $G$ 2 つの素なセットに分割する $(A,B)$, 、 どこ $A$ ソースが含まれています $s$ そして $B$ シンクが含まれています $t$. 。の $s$-コンポーネントに関する最小カットがセットになります $A$.

「最小」ということで $s$-コンポーネントの意味 $s$- カーディナリティが最小のコンポーネント。いくつか違うものがあるのではないかと思っています 最小限の $s$-コンポーネントに関するセットインクルージョン、つまり $s$- 同じ基数を持つコンポーネントですが、セットとしては等しくありません。同様に、 最小 $s$-成分;ALL にある頂点のセット $s$-コンポーネント。

Answer 1

答えはイエスだと思います。この方法で最大フローから構築された最小カットは、すべての可能な最小カットの中で可能な最小のカーディナリティも持ちます。

複数のミニカットがあり、すべて同じコストがかかります。それらは格子構造を形成します。2 つの最小カットの交差点は別の最小カットであり、2 つの最小カットの結合は別の最小カットです。すべての最小カットの交点を取ることで、この格子内の「最小」要素を特定できます。これは別の最小カットとなり、すべての最小カットの中で最小のカーディナリティを持ちます。

私の理解では、最大流量から得られる最小カットが常にこの「最小」の最小カットであることを証明することが可能です。あるいは、別の言い方をすると、ソースを考えると、 $s$ 左側とシンク $t$ 右側、次に、 $s,t$-max-flow は常に「左端」のカットになります。また、推測どおり、他の最小カットは、最大フローによって検出されたこのカットのスーパーセットになるということになります。

これらの結果およびその他の関連資料への参照については、次の質問を参照してください (注:私は個人的に検証していないため、主張の一部を自分で再確認する必要があるかもしれません)。

フォード・フルカーソンは常に左端のミニカットを生成しますか?

https://stackoverflow.com/a/8101250/781723

https://stackoverflow.com/q/26696312/781723

https://stackoverflow.com/q/9210755/781723

https://stackoverflow.com/q/41964288/781723

Answer 2

あなたの最初の質問：必ずしもそうではありません。既製のマックスフローまたは最小カットアルゴリズムは、最小のカーディナリティーではなく、任意の最小カットパーティションを生成します。しかし、マックスフローの出力があなたが望むものであるようにあなたのグラフを増やすことができます：

$ a、v \ setminus A $ と $ b、v \ setminus b $ 最小カットパーティション： <スパンクラス="数学コンテナ"> $$ \デルタ（A setminus A、V \）= \デルタ（B、V \ setminus B）=MIN_ {X \ subseteq V、S \におけるX} \デルタ（ x、v \ setminus x）$$ さて、他のすべての頂点に>重量<スパンクラス="数学コンテナ"> $ \ varepsilon> 0 $ の頂点から<スパンクラス="数学コンテナ"> $ T $ $ A $ 、 $ b $ に対応する新しいカットは、更新された重みを持っています。 <スパンクラス="数学・コンテナ"> $$ \デルタ（A、V \ setminus A）+ | A | \ CDOT \ varepsilon、\\ \デルタ（B、v \ setminus b）+ | B | \ cdot \ varepsilon $$ それぞれ。両方の項目が等しいので、2番目の用語 $ \ varepsilon | a | $ とは順序を決定します。したがって、新しいグラフの最小カットは、元のグラフの最小のカーディナリティ、最小カットパーティションです。唯一の警告は、 $ \ varepsilon $ は、新しいグラフの最小カットが元のグラフの最小カットであることを確認するために十分に小さく選択されなければなりません。 。重みが整数である場合、 $ 1 / | v | $ よりも小さい値で十分です。

（<スパンクラス="数学コンテナ"> $ \スター）$ の<スパンクラス="数学コンテナ"> $ \デルタ（X、V \ setminus X）$ の $ x $ 、 $ v \ setminus x $ の間のクロスエッジの重みの合計を表します。