フローネットワーク上のmincutの方向性

Question

mincutの誤解があるのか​​どうかわかりませんが、私はedmond-karpsを使ってフローネットワーク上のBFSを使ってmincutアルゴリズムを書いています。

残った流れA→B = 0なので、AからBへのミニカットを実行するように指示すると、A→Bのカットを持つセット{A}が生成されます）。

しかし、私がBからAへのミニカットを行うと言うと、（Cからのエッジがないので）エッジを増やさないので、結果のセットは{C}であり、カットB→C（2）となる。

私はそれを見て、私は2つの方法の1つでこれを誤解する可能性があります。まず、BからAへのミニカットは正しいかもしれません.Bのセットからのエッジだけがカウントされ、エッジではありません（つまり、ミニカットは「BがAに接続するのを許可しない最小限のものです」、

また、フローネットワーク上でmincutを探すように求められている場合（一般的な最小カット、現在「任意のソースを選んでいる」、他のすべてのノード」法）、それは任意のエッジ上の両方向に等しい流量を必要としなければならない。

Answer 1

分カット 『正しい』は、 『試してソース= B = A』があるため、0であり、シンクエッジB-> A（等価的に、c（B、A）= 0）はありません;それはあなたのimpのように見えます他の質問に答えるかもしれない。それがシンクで終わることを確実にするために、BFSステージの潜在的な最短パスを確認していますか？ 。

（mincutは何が2つのパーティションにグラフ を分割する最小むしろ」より、「Aに接続 にBを許可しないように最小であるものを」求めていることを意味する）

はい、最初のもの：ソースからシンクまでのボトルネックを気にします（最大流量min-cut定理）。最小カットグラフを2つに分割しますが、ソースシンクは別々のセットにあります。

これを「シンクとして他のすべてのノードを扱う」と言っている場合

（私は現在、「他のすべてのノードを試してみてください、任意のソースを選ぶ」方法を使用している一般的な最小カット、）ソースの外縁部の単純度計算です。

編集：エッジは重み付けされているため正確な度数計算ではありませんが、エッジウェイトを加算するだけで検索は必要ありません。

いずれのエッジでも両方向に同じフローが必要です。 （ - 任意の無向エッジが2つの逆平行エッジにマッピングされ、特定のフローの問題のために、エッジの一方のみが使用されるフローネットワークは、グラフを向いている）

は

そのような要件は存在しません。