ソースとシンクを分離する無向グラフの最小カットを見つけるアルゴリズムはありますか

Question

私はエッジ加重無向グラフと2つのノード（しばしばソースとシンクと呼ばれます）を持っています。これら2つのノードを2つの弱い成分に分ける最小限の重みの辺の集合を見つける必要があります。

私は有向グラフについて約maximum flow and minimum cut relationについて約Ford-Fulkerson's maximum flow algorithmと彼の定理について知っています。

また、無向グラフのためのFord-Fulkersonの最大フローアルゴリズムの変更についても知っています。無向グラフは、それぞれの無向エッジを2つの対向する有向エッジで置き換え、両方のフローを同時に更新します。しかし、この変更で、最大フロー・最小カット定理は以下の無向グラフ上の最小カットが正しく判定されないので、もはや有効ではないようだ。

nodes: 0, 1, 2, 3 
edges & capacities: {0,1}->5, {0,2}->6, {1,2}->2, {1,3}->7, {2,3}->4 
source: 0 
sink: 3 

最大フロー分カットの定理によると、最小カットは、それらの能力に等しいフローであり、修正されたFord-Fulkersonによって、すべてのエッジであり、明らかに正しいカットではありません。

無向グラフではStoer–Wagner algorithm for finding a global minimum cutが見つかりましたが、このアルゴリズムではソースとシンクが考慮されておらず、ノードが同じコンポーネント内にあるようにカットを見つけることができないため、

ソースとシンクを持つ無向グラフの最小カットを効率的に見つけ出し、指定した2つのノードを分離できるアルゴリズムはありますか？ 多分私の場合にそれらを働かせるために以前に言及されたアルゴリズムを修正することができますか？

Answer 1

Ford-Fulkersonのアルゴリズムをいくつか変更することができます。

1. まずソースとシンクの間の最大のフローを見つけてそれを覚えておく必要があります。
2. グラフからエッジを削除します。
3. 次に、新しいグラフで最大のフローを見つける必要があります。最大流量がステップ1と同じでない場合、このエッジは最小限のカットになります。グラフへ
4. 戻りエッジは、ちょうど同じ容量を持つ2つの有向エッジとして無向辺を考慮し、いくつかの他のエッジを選択して、あなたが最大のフローを見つけた場合2.

に進みます。