5

エッジ加重無向グラフと 2 つのノード (ソースとシンクと呼ばれることが多い) があります。これらの 2 つのノードを 2 つの弱いコンポーネントに分離する、可能な限り最小の重みのエッジのセットを見つける必要があります。

Ford-Fulkerson の最大フロー アルゴリズムと、有向グラフの最大フローと最小カット関係に関する彼の定理については知っています。

また、Ford-Fulkerson の無向グラフの最大フロー アルゴリズムの修正についても知っています。これは、各無向エッジを 2 つの反対の有向エッジに置き換え、両方へのフローを同時に更新します。しかし、この変更により、max-flow-min-cut-theorem は有効ではなくなったように見えます。これは、次の無向グラフで最小カットが正しく決定されないためです。

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

max-flow-min-cut の定理によると、最小カットはそれらのエッジであり、フローはその容量に等しく、変更された Ford-Fulkerson によってそれはすべてのエッジであり、明らかに正しいカットではありません。

無向グラフでグローバル最小カットを見つけるためのStoer-Wagner アルゴリズムを見つけましたが、このアルゴリズムはソースとシンクを考慮せず、ノードを配置できるカットを見つけることができるため、これは私が望むものではありません。同じコンポーネント。

これら2つの指定されたノードを分離して、ソースとシンクを持つ無向グラフで最小カットを効率的に見つけることができるアルゴリズムはありますか? 前述のアルゴリズムを変更して、私のケースで機能するようにすることはできますか?

4

2 に答える 2

0

Ford-Fulkerson のアルゴリズムのいくつかの変更を使用できます。

  1. まず、ソースとシンクの間の最大フローを見つけて、それを記憶する必要があります。
  2. グラフから一部のエッジを削除します。
  3. 次に、新しいグラフで最大フローを見つける必要があります。最大フローがステップ 1 と同じでない場合、このエッジは最小カットにあります。
  4. エッジをグラフに戻し、別のエッジを選択してステップ 2 に進みます。

最大フローを見つけるときは、無向エッジを同じ容量を持つ 2 つの有向エッジと考えてください。

于 2016-04-27T04:01:57.490 に答える
0

max-flow-min-cut 定理によると、最小カットはそれらのエッジであり、そのフローはその容量に等しい...

これは正しくありません。あなたはすでに反例を与えました。最大フローから最小カットを見つけるための正しいアルゴリズムは、この投稿に記載されています。ここに引用します。

最小カットは、ノードを 2 つのグループに分割することです。

最大フローを見つけたら、残差グラフを作成して最小カットを見つけることができます。ソースから到達可能なすべてのノードまでこの残差ネットワークをたどると、これらのノードはパーティションの一部を定義します。このパーティションを A と呼びます。残りのノード (到達不能ノード) は B と呼ぶことができます。最小カットのサイズは、A のノードから A のノードに流れる元のネットワークのエッジの重みの合計です。 B.

したがって、あなたが言ったように、各エッジを 2 つの反対方向のエッジに変換し、新しいグラフで最大フローを計算してから、上記のアルゴリズムを使用して最大フローを最小カットに変換できます。

于 2021-07-20T08:16:37.470 に答える