最大流量が与えられたmin cutを見つけるアルゴリズム

誰も私にf（v）[w]が最大であるグラフ（V、E、c、s、t、f）のmin cutを見つけるアルゴリズムについて考えてもらえますか？フローとc [v] [w]は容量ですか？最大流量が与えられたmin cutを見つけるアルゴリズム

2012-03-07 user1247412

Google？そこにはたくさんのものがありますが、何が問題になっていますか？ –

の可能な複製[最大フローアルゴリズムを使用してグラフの最小カットを見つける方法はありますか？]（http://stackoverflow.com/questions/4482986/how-can-i-find-the-minimum-cut-on -a-graph-using-a-maximum-flow-algorithm） –

これは本当の質問です。それを閉じた人は、max-flow min-cut定理を理解していない。 – wcochran

ソースノードからBFSまたはDFSを実行します。あなたが右に行くことができないエッジは、ミニカットに座っています。エッジをトラバースするときは、c[v][w] > f[v][w]をチェックする必要があります。到達可能なノードは最小カットの左側にあり、他のノードは右側にあります。

出典

2012-03-07 11:49:26

詳細については、[こちら]（http://www.google.com/url?sa=t&rct=j&q=&esrc=s&source=web&cd=1&cts=1331121392192&ved=0CC4QFjAA&url=http%3A%2F%2Fciteseerx.ist）をご確認ください。 psu.edu％2Fviewdoc％2Fdownload％3Bjsessionid％3D6F1324E4CAF290676E3605F39901D1A4％3Fdoi％3D10.1.1.85.7307％26rep％3Drep1％26type％3Dpdf＆EI = tkxXT7v-EsrJrAeZwLXzCw＆USG = AFQjCNHlUpzr2bHRgY9ecDnxpKDyRgp9Pw＆SIG2 = 6P1qlsU54JAjBmMVScfd7Q） –

http://ezekiel.vancouver.wsu.edu/~ cs223/lectures/graphs/maxflow/maxflow.pdf – wcochran

注：自分でアルゴリズムを実装したくない場合。そして、私はあなたが勉強したいだけでなく、JGraphTライブラリを使いたいのでなければ、あなたがしないことをお勧めします。完全に解決された問題 - 完全に洗練されたAPIを介してMaxFlowとMinCutがすべて提供されました。 – 99Sono

最大流量が与えられたmin cutを見つけるアルゴリズム

答えて

関連する問題