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

Question

無向グラフで最大フローを見つけるためにどのアルゴリズムを使用する必要があるかを誰かが知っていますか?

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

しかし、マルチグラフの場合はどのように処理すればよいでしょうか?

Answer 1

方向性のないエッジがある場合

     5
* ------ *

次に、それを 2 つの方向付けられたエッジに変えることができます。

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

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