0

Ford-Fulkerson アルゴリズムの私の分析は正しく出ていません。たとえば、次のグラフを見てください。

      _____>4___>_
     |            |
0--->1---->3------6
|    |            | 
2--->5--------->---

ノード 0 はソース、ノード 6 はターミナル ノードであり、すべてのエッジの制限は 1 です。ただし、ノード 0 から 1 へのエッジの制限は 2 です。フローが 0->1->3->6 および 0- >1->4->6 および 0->2->5->6 の場合、グラフのフローは 3 です。ただし、フローが 0->1 から開始する場合は、0->1->3 を選択します。 ->6 と 0->1->5->6 では、5->6 は既に占有されているため、0->2->5->6 からはもう移動できません。0->1 の制限は 2 であるため、0->1 から開始できるのは 2 回だけです。したがって、グラフのフローは 2 です。明らかに、グラフの可能な最大フローは 2 ではなく 3 である必要があります。アルゴリズムはこの問題を処理し、常に答えとして 3 を返しますか?

4

2 に答える 2

1

はい、フォード・フルカーソンはできます。このような問題を常に解決することは、実際にはそのために設計されたものです。

あなたが見逃しているという事実は、残差グラフを決定するときにバックエッジも追加する必要があるということだと思います。したがって、0->1->3->6 および 0->1->5->6 に進むと、残差グラフは実際には次のようになります。

                1          1
            +-------> 4 ------+
            |                 |
        2   |     1        1  v
  0 <------ 1 <----- 3 <----- 6
  |         ^                 |
  |   1     | 1               | 1
  +-------> 5 <---------------+

Ford-Fulkerson が取ろうとしている次のステップは、ルート 0->5->1->4->6 を追加することであり、したがって 3 のフローが得られます。

于 2013-03-04T21:46:52.183 に答える