フォード・フルカーソンアルゴリズム

Algorithm to compute the maximum flow in a network

フォード・ファルカーソン法またはフォード・ファルカーソンアルゴリズム（FFA）は、フローネットワークの最大フローを計算する貪欲アルゴリズムです。残差グラフにおける増加パスの探索手法が完全には規定されていないため^[1]、あるいは実行時間が異なる複数の実装が規定されているため、 ^[2]「アルゴリズム」ではなく「手法」と呼ばれることもあります。この手法は1956年にLRフォード・ジュニアとDRファルカーソンによって発表されました。^[3] 「フォード・ファルカーソン」という名称は、フォード・ファルカーソン法の完全に定義された実装であるエドモンズ・カープアルゴリズムにもしばしば使用されます。

このアルゴリズムの背後にある考え方は次のとおりです。ソース（開始ノード）からシンク（終了ノード）へのパスが存在し、パス上のすべてのエッジに利用可能な容量がある場合、フローをいずれかのパスに沿って送信します。次に、別のパスを見つけ、これを繰り返します。利用可能な容量を持つパスは、増加パスと呼ばれます。

アルゴリズム

グラフを u とし、 u から v への各辺について、を容量、をフローとする。ソースsからシンクtへの最大フローを求める。アルゴリズムの各ステップにおいて、以下の式が成り立つ。 ${\displaystyle G(V,E)}$ ${\displaystyle c(u,v)}$ ${\displaystyle f(u,v)}$

容量制約	${\displaystyle \forall (u,v)\in E:\ f(u,v)\leq c(u,v)}$	エッジに沿ったフローはその容量を超えることはできません。
歪んだ対称性	${\displaystyle \forall (u,v)\in E:\ f(u,v)=-f(v,u)}$	uからvへの純フローは、vからuへの純フローの反対である必要があります(例を参照)。
フローの保存	${\displaystyle \forall u\in V:u\neq s{\text{ and }}u\neq t\Rightarrow \sum _{w\in V}f(u,w)=0}$	フローを「生成」するソースと、フローを「消費」するシンクを除き、ノードへのネット フローはゼロになります。
値(f)	${\displaystyle \sum _{(s,u)\in E}f(s,u)=\sum _{(v,t)\in E}f(v,t)}$	sから出ていくフローはtに到着するフローと等しくなければなりません。

これは、アルゴリズムの各ラウンドの後に、ネットワークを通過するフローが合法的なフローになることを意味します。残余ネットワークを 、容量がありフローがないネットワークと定義します。vからuへのフローが、元のネットワークでは許可されていないにもかかわらず、残余ネットワークでは許可される場合があることに注意してください。 ${\displaystyle G_{f}(V,E_{f})}$ ${\displaystyle c_{f}(u,v)=c(u,v)-f(u,v)}$ ${\displaystyle f(u,v)>0}$ ${\displaystyle c(v,u)=0}$ ${\displaystyle c_{f}(v,u)=c(v,u)-f(v,u)=f(u,v)>0}$

アルゴリズムフォード・フルカーソン

入力 フロー容量c、ソースノードs、シンクノードtを持つネットワーク が与えられている ${\displaystyle G=(V,E)}$

出力 sからtへの最大値のフローfを計算する

1. ${\displaystyle f(u,v)\leftarrow 0}$すべてのエッジについて ${\displaystyle (u,v)}$
2. にはsからtへのパスp があり、すべてのエッジに対して次のようになります。 ${\displaystyle G_{f}}$ ${\displaystyle c_{f}(u,v)>0}$ ${\displaystyle (u,v)\in p}$
   1. 探す ${\displaystyle c_{f}(p)=\min\{c_{f}(u,v):(u,v)\in p\}}$
   2. 各エッジについて ${\displaystyle (u,v)\in p}$
      1. ${\displaystyle f(u,v)\leftarrow f(u,v)+c_{f}(p)}$（パスに沿ってフローを送信します）
      2. ${\displaystyle f(v,u)\leftarrow f(v,u)-c_{f}(p)}$（フローは後で「返される」可能性があります）

• 「←」は代入を表します。例えば、「biggest ← item 」は、 biggest の値がitemの値に変更されることを意味します。
• 「return」はアルゴリズムを終了し、次の値を出力します。

ステップ2のパスは、例えば幅優先探索（BFS）や深さ優先探索によって見つけることができます。前者はエドモンズ・カープアルゴリズムとして知られています。 ${\displaystyle G_{f}(V,E_{f})}$

ステップ2でこれ以上の経路が見つからない場合、残余ネットワークにおいてs はtに到達できなくなります。残余ネットワークにおいてsが到達可能なノードの集合をSとすると、元のネットワークにおけるSからVの残りの部分へのエッジの総容量は、一方ではsからtへの総フローに等しく、他方ではそのようなフローすべての上限として機能します。これは、我々が発見したフローが最大であることを証明しています。最大フロー・最小カット定理も参照してください。

グラフに複数のソースとシンクがある場合、次のように動作します。 とと仮定します。からすべてのノード への辺を持つ新しいソースを追加します。容量は です。 また、すべてのノード からへの辺を持つ新しいシンクを追加します。容量は です。 次に、Ford–Fulkerson アルゴリズムを適用します。 ${\displaystyle G(V,E)}$ ${\displaystyle T=\{t\mid t{\text{ is a sink}}\}}$ ${\displaystyle S=\{s\mid s{\text{ is a source}}\}}$ ${\displaystyle s^{*}}$ ${\displaystyle (s^{*},s)}$ ${\displaystyle s^{*}}$ ${\displaystyle s\in S}$ ${\displaystyle c(s^{*},s)=d_{s}=\sum _{(s,u)\in E}c(s,u)}$ ${\displaystyle t^{*}}$ ${\displaystyle (t,t^{*})}$ ${\displaystyle t\in T}$ ${\displaystyle t^{*}}$ ${\displaystyle c(t,t^{*})=d_{t}=\sum _{(v,t)\in E}c(v,t)}$

また、ノードu に容量制約 がある場合、このノードを容量 を持つ2 つのノードと 1 つのエッジに置き換えます。その後、Ford–Fulkerson アルゴリズムを適用できます。 ${\displaystyle d_{u}}$ ${\displaystyle u_{\mathrm {in} },u_{\mathrm {out} }}$ ${\displaystyle (u_{\mathrm {in} },u_{\mathrm {out} })}$ ${\displaystyle c(u_{\mathrm {in} },u_{\mathrm {out} })=d_{u}}$

複雑

フロー増加パスをグラフ内にすでに確立されているフローに追加することで、グラフ内にそれ以上のフロー増加パスが見つからなくなったときに最大フローに到達します。 ただし、この状況に必ず到達するという保証はないため、アルゴリズムが終了した場合に答えが正しいことが保証されるのが最善です。 アルゴリズムが終了しない場合は、フローが最大フローに収束しない可能性があります。 ただし、この状況は無理数のフロー値でのみ発生します。^[4] 容量が整数の場合、Ford–Fulkerson の実行時間は( big O 表記 を参照) で制限されます。ここで、はグラフ内のエッジ数、はグラフ内の最大フローです。 これは、各増加パスが時間内に見つかり、フローが少なくとも の整数量増加し、上限が であるためです。 ${\displaystyle O(Ef)}$ ${\displaystyle E}$ ${\displaystyle f}$ ${\displaystyle O(E)}$ ${\displaystyle 1}$ ${\displaystyle f}$

終了が保証され、実行時間が最大フロー値に依存しない Ford–Fulkerson アルゴリズムのバリエーションとして、時間内で実行されるEdmonds–Karp アルゴリズムがあります。 ${\displaystyle O(VE^{2})}$

整数フローの例

以下の例は、4つのノード（ソースとシンク ）を持つフローネットワークにおけるFord–Fulkerson法の最初のステップを示しています。この例は、アルゴリズムの最悪ケースの動作を示しています。各ステップでは、 のフローのみがネットワークを介して送信されます。代わりに幅優先探索を使用すれば、必要なステップは2つだけです。 ${\displaystyle A}$ ${\displaystyle D}$ ${\displaystyle 1}$

ステップ	フローネットワーク
初期フローネットワーク。
フローは増加パスに沿って送られます。ここでボトルネックとなるのは-エッジなので、フローは1ユニットのみ可能です。 ${\displaystyle A,B,C,D}$ ${\displaystyle B}$ ${\displaystyle C}$
ここで、1単位のフローが増加経路 に沿って送られます。この場合、フローは から へ「押し戻され」ます。元々 から へ流れ込んでいたフローは、今では からへ流れ込むため、 に直接フローを送ることができます。その結果、-エッジのフローはゼロになりますが、全体のフローは1増加します。 ${\displaystyle A,C,B,D}$ ${\displaystyle C}$ ${\displaystyle B}$ ${\displaystyle C}$ ${\displaystyle B}$ ${\displaystyle A}$ ${\displaystyle B}$ ${\displaystyle D}$ ${\displaystyle B}$ ${\displaystyle C}$
1998 年の中間ステップはここでは省略します。
合計フローが 2000 ユニットの最終フロー ネットワーク。

終了しない例

右に示すフローネットワークを考えてみましょう。ソース、シンク、エッジの容量はそれぞれ、および、であり、その他のエッジの容量は整数です。定数は、となるように選択されています。拡張パスは、次の表に従って使用します。ここで、、およびです。 ${\displaystyle s}$ ${\displaystyle t}$ ${\displaystyle e_{1}=1}$ ${\displaystyle e_{2}=r=({\sqrt {5}}-1)/2}$ ${\displaystyle e_{3}=1}$ ${\displaystyle M\geq 2}$ ${\displaystyle r}$ ${\displaystyle r^{2}=1-r}$ ${\displaystyle p_{1}=\{s,v_{4},v_{3},v_{2},v_{1},t\}}$ ${\displaystyle p_{2}=\{s,v_{2},v_{3},v_{4},t\}}$ ${\displaystyle p_{3}=\{s,v_{1},v_{2},v_{3},t\}}$

ステップ	増強パス	送信フロー	残存容量
			${\displaystyle e_{1}}$	${\displaystyle e_{2}}$	${\displaystyle e_{3}}$
0			${\displaystyle r^{0}=1}$	${\displaystyle r}$	${\displaystyle 1}$
1	${\displaystyle \{s,v_{2},v_{3},t\}}$	${\displaystyle 1}$	${\displaystyle r^{0}}$	${\displaystyle r^{1}}$	${\displaystyle 0}$
2	${\displaystyle p_{1}}$	${\displaystyle r^{1}}$	${\displaystyle r^{0}-r^{1}=r^{2}}$	${\displaystyle 0}$	${\displaystyle r^{1}}$
3	${\displaystyle p_{2}}$	${\displaystyle r^{1}}$	${\displaystyle r^{2}}$	${\displaystyle r^{1}}$	${\displaystyle 0}$
4	${\displaystyle p_{1}}$	${\displaystyle r^{2}}$	${\displaystyle 0}$	${\displaystyle r^{1}-r^{2}=r^{3}}$	${\displaystyle r^{2}}$
5	${\displaystyle p_{3}}$	${\displaystyle r^{2}}$	${\displaystyle r^{2}}$	${\displaystyle r^{3}}$	${\displaystyle 0}$

ステップ 1 の後だけでなくステップ 5 の後でも、エッジ、、の残余容量は、それぞれ、ある に対して、 、 、 という形式になっていることに注意してください。これは、増加パス、、を無限回使用でき、これらのエッジの残余容量は常に同じ形式になることを意味します。ステップ 5 後のネットワークの合計フローは です。上記のように増加パスを使用し続けると、合計フローは に収束します。ただし、に沿って 単位のフロー、 に沿って 1 単位のフロー、に沿って 単位のフローを送信することにより、値 のフローが発生することに注意してください。したがって、アルゴリズムが終了することはなく、フローは最大フローに収束しません。^[5] ${\displaystyle e_{1}}$ ${\displaystyle e_{2}}$ ${\displaystyle e_{3}}$ ${\displaystyle r^{n}}$ ${\displaystyle r^{n+1}}$ ${\displaystyle 0}$ ${\displaystyle n\in \mathbb {N} }$ ${\displaystyle p_{1}}$ ${\displaystyle p_{2}}$ ${\displaystyle p_{1}}$ ${\displaystyle p_{3}}$ ${\displaystyle 1+2(r^{1}+r^{2})}$ ${\displaystyle \textstyle 1+2\sum _{i=1}^{\infty }r^{i}=3+2r}$ ${\displaystyle 2M+1}$ ${\displaystyle M}$ ${\displaystyle sv_{1}t}$ ${\displaystyle sv_{2}v_{3}t}$ ${\displaystyle M}$ ${\displaystyle sv_{4}t}$

ユークリッドアルゴリズムに基づくもう1つの非終了例は、 Backman & Huynh (2018) によって示されています。この例では、順序数のネットワーク上での Ford-Fulkerson アルゴリズムの最悪ケースの実行時間がであることも示されています。 ${\displaystyle G(V,E)}$ ${\displaystyle \omega ^{\Theta (|E|)}}$

Edmonds-KarpアルゴリズムのPython実装

コレクションをインポートする クラスGraph :  「」 このクラスは有向グラフを表現する。 隣接行列表現。 「」 def __init__ ( self 、graph ):   self . graph  =  graph  # 残差グラフ self.row = len (グラフ)​​   def bfs ( self 、s 、t 、parent ):     「」 パスがある場合はtrueを返します 残差グラフのソース 's' からシンク 't' へ。 また、パスを保存するためにparent[]を入力します。 「」 # すべての頂点を未訪問としてマークする 訪問 =  [ False ]  * 自己.行 # BFS用のキューを作成する キュー = コレクション。デク() # ソースノードを訪問済みとしてマークし、キューに追加します キュー.追加( s ) 訪問[ s ]  =  True # 標準BFSループ  キュー中: u  = キュー. popleft () # キューから外された頂点 u の隣接する頂点をすべて取得する # 隣接した場所がまだ訪問されていない場合は、マークを付けます # 訪問してキューに追加  enumerate ( self . graph [ u ] )内のind 、 val について:   訪問した[ ind ]  ==  Falseかつ val > 0の 場合:   キュー.append ( ind )​ 訪問済み[ ind ]  =  True 親[ ind ]  =  u # ソースからBFSのシンクに到達した場合は、戻ります # 真、そうでない場合は偽  訪問した戻る[ t ] # 与えられたグラフにおける s から t への最大フローを返します edmonds_karpの定義( self 、source 、sink ):    # この配列はBFSによって埋められ、パスを格納する 親 =  [ - 1 ]  * 自己.行 max_flow  =  0  # 最初はフローはありません # ソースからシンクへのパスがある間にフローを増強する  self.bfs ( source , sink , parent )の場合:   # エッジの最小残余容量を求める # BFSで埋められたパス。あるいは最大フローを求めるとも言える。 # 見つかったパスを通過します。 path_flow  =  float ( "Inf" ) s  = シンク  s  != ソースの場合: path_flow  =  min ( path_flow ,  self . graph [ parent [ s ]][ s ]) s  = 親[ s ] # 全体のフローにパスフローを追加する 最大フロー += パスフロー # エッジとリバースエッジの残余容量を更新します # 道沿い v  = シンク  v  != ソースの場合: u  = 親[ v ] 自己.グラフ[ u ][ v ]  -= パスフロー 自己.グラフ[ v ][ u ]  += パスフロー v  = 親[ v ]  max_flowを返す

参照

• ベルジュの定理
• 近似最大フロー最小カット定理
• ターン制限ルート
• ディニックのアルゴリズム

注記

1. Laung-Terng Wang, Yao-Wen Chang, Kwang-Ting (Tim) Cheng (2009). 『電子設計自動化：合成、検証、テスト』 Morgan Kaufmann. pp. 204. ISBN 978-0080922003。{{cite book}}: CS1 maint: multiple names: authors list (link)
2. トーマス・H・コーメン;チャールズ・E・ライザーソン。ロナルド・L・リベスト。クリフォード・スタイン (2009)。アルゴリズムの概要。 MITプレス。ページ714。ISBN 978-0262258104。
3. Ford, LR ; Fulkerson, DR (1956). 「ネットワークを通じた最大フロー」(PDF) . Canadian Journal of Mathematics . 8 : 399–404 . doi :10.4153/CJM-1956-045-5. S2CID  16109790.
4. Ford -Fulkerson最大フローラベリングアルゴリズム」1998年。CiteSeerX 10.1.1.295.9049。 
5. Zwick, Uri (1995年8月21日). 「フォード・フルカーソン最大フロー法が停止しない可能性のある最小ネットワーク」.理論計算機科学. 148 (1): 165– 170. doi : 10.1016/0304-3975(95)00022-O .

参考文献

• コーメン, トーマス・H. ;レイサーソン, チャールズ・E. ;リベスト, ロナルド・L. ;スタイン, クリフォード(2001). 「第26.2節 フォード・フルカーソン法」アルゴリズム入門（第2版）. MIT Press and McGraw-Hill. pp.  651– 664. ISBN 0-262-03293-7。
• ジョージ・T・ハイネマン、ゲイリー・ポリス、スタンレー・セルコウ (2008). 「第8章 ネットワークフローアルゴリズム」. 『Algorithms in a Nutshell 』 . Oreilly Media . pp.  226– 250. ISBN 978-0-596-51624-6。
• ジョン・クラインバーグ、エヴァ・タルドス(2006). 「第7章：最大フロー問題への拡張」.アルゴリズム設計. ピアソン・エデュケーション. pp. 378–384. ISBN 0-321-29535-8。
• サミュエル・グテクンスト（2019）。エングリ 1101。コーネル大学。
• バックマン、スペンサー；フイン、トニー (2018). 「有限ネットワーク上の超限フォード・フルカーソン」.計算可能性. 7 (4): 341– 347. arXiv : 1504.04363 . doi :10.3233/COM-180082. S2CID  15497138.

外部リンク

• 最大フロー問題を解くためのフォード・フルカーソン法を説明するチュートリアル
• もう1つのJavaアニメーション
• Java Web Startアプリケーション

ウィキメディア・コモンズにおけるフォード・フルカーソンのアルゴリズムに関連するメディア

Retrieved from "https://en.wikipedia.org/w/index.php?title=Ford–Fulkerson_algorithm&oldid=1323732383"