algorithm - Ford-Fulkerson アルゴリズムでバック エッジが必要なのはなぜですか?

Question

グラフの最大フローを見つけるには、バック エッジを考慮せずに、そのパスの最小エッジ キャパシティですべての拡張パスを飽和させるだけで十分ではないのはなぜですか? つまり、そこからの流れを想定した場合、それをバックエッジと呼ぶ点は何ですか?

Answer 1

Ford-Fulkerson アルゴリズムを実行する場合、選択したパスが全体的なフローの一部でなくなる場合に備えて、バック エッジが必要です。

バック エッジが必要な例として、次のフロー ネットワークを考えてみましょう。

    s
   / \
  a   b
   \ / \
    c   d
     \ /
      t

すべての辺が下向きで、すべての辺の容量が 1 で、s から t への流れを見つけたいとします。Ford-Fulkerson の最初の反復で、パス s → b → c → t を取るとします。この時点で、フローの 1 単位を s から t にプッシュしました。バックエッジを追加しないと、次のようになります。

    s
   / 
  a   b
   \   \
    c   d
       /
      t

これ以上 st パスはありませんが、それは最大フローがあるという意味ではありません。パス s → a → c → t に沿って 1 つを送信し、パス s → b → d → t に沿って 1 つを送信することにより、2 つのフローの単位を s から t にプッシュできます。残差フロー ネットワークにバック エッジがなければ、この別のパスを発見することはできません。

お役に立てれば！