0

mincut の誤解があるかどうかはわかりませんが、edmond-karps とそれに続くフロー ネットワーク上の BFS を使用して mincut アルゴリズムを作成しました。

A から B への最小カットを実行するように指示すると、残差フロー A->B = 0 であるため機能し、A->B (1) のカットでセット {A} が生成されます。

ただし、B から A への最小カットを実行するように指示した場合、(C からのエッジがないため) エッジを拡張することはできません。そのため、結果のセットは {C} であり、B-> のカットがあります。 C (2)。

私の見方では、これを 2 つのうちの 1 つの方法で誤解している可能性があります。まず、B から A への最小カットは正しい可能性があります。これは、B のセットからのエッジのみがカウントされ、エッジへのエッジはカウントされないためです (つまり、最小カットは、「B が A に接続できないようにするための最小値は何か」ではなく、"グラフを 2 つのパーティションに分割するための最小値は何ですか)。

または、フロー ネットワークで最小カットを見つけるように求められた場合 (一般的な最小カット。現在、「任意のソースを選択し、他のすべてのノードを試す」方法を使用しています)、両方向に等しいフローが必要である必要があります。任意のエッジ。

サンプルグラフ

4

1 に答える 1

1

「ソース=B、シンク=A」の「正しい」最小カットは 0 です。エッジ B->A がないためです (同等に、c(B, A) = 0)。あなたの実装は別の質問に答えているようです。BFS ステージで可能な最短パスをそれぞれチェックして、シンクで終了することを確認していますか?

(mincut は、「グラフを 2 つのパーティションに分割するための最小値は何か」ではなく、「B が A に接続できないようにするための最小値は何か」を尋ねていることを意味します)。

はい、最初の 1 つ: ソースからシンクまでのボトルネックのみを考慮します (最大フロー最小カット定理)。最小カットはグラフを 2 つに「分割」しますが、ソースとシンクが別々のセットにあるという追加の要件があります。

（一般的な最小カット。現在、「任意のソースを選択し、他のすべてのノードを試す」方法を使用しています）

「他のすべてのノードをシンクとして扱う」と言っている場合、これはソースの外側のエッジに対する単純な次数計算です。

編集：エッジが重み付けされているため、正確には次数の計算ではありませんが、エッジの重みを合計しているだけで、検索は必要ありません。

どのエッジでも両方向に等しい流れが必要です。

そのような要件はありません (フロー ネットワークは有向グラフです。無向エッジは 2 つの逆平行エッジにマッピングされ、特定のフローの問題ではエッジの 1 つだけが使用されます)。

于 2016-05-20T03:23:02.060 に答える