最大フローグラフアルゴリズム

Question

どのアルゴリズムを使用して、 オリエント グラフ？

私が理解している限り、ここの指向のないネットワークは基本的にグラフをマルチグラフに変え、頂点は2つで接続されています "普通" rib骨と2つ "偽" たとえばで使用されるrib骨 Ford-Fulkerson アルゴリズム。

しかし、マルチグラフのケースをどのように処理する必要がありますか？

Answer 1

オリエントのエッジがある場合

     5
* ------ *

次に、2つの方向のエッジに変えることができます。

     5
  ------>
*         *
  <------
     5

Ford-Fulkersonメソッドは、このようなグラフで完全に機能します。