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

Question

グラフ内の最大フローを見つけるには、バックエッジを考慮せずに、そのパス内の最小エッジ容量ですべての拡張パスを飽和させるだけで十分ではありませんか？私はそれからの流れを仮定すると、それは後端と呼ぶ点は何ですか？

Answer 1

選択したパスが最終的なフローの一部ではない場合に、Ford-Fulkersonアルゴリズムを実行するときに、バックエッジが必要です。

バックエッジが必要であり、このフローネットワークを考える例として：

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

は、すべてのエッジがダウンポイントとすべてのエッジが容量1を持っていて、T秒からの流れを見つけたいということと仮定。 Ford-Fulkersonの最初の反復で、s→b→c→tの経路を取るとします。この時点で、sからtへの1単位のフローをプッシュしました。あなたが任意のバックエッジには追加しない場合、あなたはこれで左にしている：

s 
/
    a b 
    \ \ 
    c d 
    /
     t 

そこにはより多くのS-Tのパスはありませんが、それはあなたが最大の流れを持って意味するものではありません。 s→a→c→tの経路とs→b→d→tの経路に沿って、2つの単位フローをsからtにプッシュすることができます。残りのフローネットワークにバックエッジがなければ、この他のパスは決して見つけられません。

希望すると便利です。