無向加重グラフがあり、頂点の 2 つのセットを分離する最小カットを見つける必要があります。2 つの頂点を分離する最小カットを見つける問題を軽減するために、セットアップを変更できます。重みが正の分数であることを付け加えておきます。
Stoer-Wagner アルゴリズムは、指定されたノードをカットの異なる側に保持すること以外はすべて行います。それを行うために SW を変更する方法があるかどうか、私は興味がありました。
ありがとうございました。
1 に答える
1
Stoer-Wagner についてはわかりませんが、この問題を解決するもう 1 つの典型的な方法は、MaxFlow を使用することです。
ノードの 1 つのセットをソースにリンクし、もう 1 つのノードを宛先に無制限の容量でリンクします。他のすべてのエッジは 1 の重みを持つ必要があり、結果のグラフで MaxFlow を実行します。
完了したら、残りのネットワークでソースからまだアクセスできるすべてのノードをマークします (最後のパス検索実行でアクセスしたノード)。元のグラフのマークされたノードとマークされていないノードの間にあるエッジは、最小カットの一部です。
于 2016-03-31T08:07:05.893 に答える