最大フロー問題

最大フロー問題（さいだいフローもんだい、英: Maximum flow problem）または最大流問題とは、単一の始点から単一の終点へのフローネットワークで最大となるフローを求める問題である^[1]。単にフローの最大値を求める問題と定義されることもある。最大フロー問題は、より複雑なネットワークフロー問題である最小費用流問題の特殊ケースと見ることもできる。

最小カット問題（英: Minimum cut problem）とは、辺の重みが非負値の有向グラフにおいて、始点から終点までのパスが存在しなくなるように辺を除去した時に、除去した辺の重みの総和を最小にする問題。始点から終点への最大フローは始点から終点への最小カットと等しい。これを最大フロー最小カット定理と呼ぶ。

2部グラフの最大マッチング問題（英: Maximum bipartite matching）とは、2部グラフの最大マッチングを求める問題で、これも最大フロー問題のアルゴリズムを使用して解ける^[1]。

解法

有向グラフ ${\displaystyle G(V,E)}$ において、各枝 ${\displaystyle u,v}$ の容量を ${\displaystyle c(u,v)}$ としたとき、始点 ${\displaystyle s}$ から終点 ${\displaystyle t}$ への最大フロー ${\displaystyle f}$ を求める。この問題の解法アルゴリズムは多数存在する。

発表年	名称	計算量	説明
	線形計画法		正規フローの定義から制約条件が与えられる。${\displaystyle \sum _{v\in V}f(s,v)}$ を最大化。
1956年	フォード・ファルカーソンのアルゴリズム	${\displaystyle O(E\cdot {\text{maxflow}})}$	残余グラフに余裕がある限り、その経路の残余容量の最小ぶんだけ送る。この計算量を達成するには、容量の整数性が必要である。容量が無理数を含む場合、終了しない可能性がある。
1970年	エドモンズ・カープのアルゴリズム	${\displaystyle O(VE^{2})}$	フォード・ファルカーソンの特殊ケースであり、幅優先探索で増加道を探す。
1970年	Dinic法	${\displaystyle O(V^{2}E)}$	ステップ毎に残余グラフについて幅優先探索で層別グラフを構築し、この上でブロッキングフローと呼ばれるフローを求め、これを追加する。層別グラフでのブロッキングフローは ${\displaystyle O(VE)}$ で求められ、ステップの反復は最大 ${\displaystyle n-1}$ 回である。
1978年	MPM法[2]	${\displaystyle O(V^{3})}$	Malhotra, Pramodh-Kumar, Maheshwari が発表。
1981年	動的木を使ったDinic法[3]	${\displaystyle O(VE\log V)}$	層別グラフのブロッキングフロー計算を動的木を使うことで ${\displaystyle O(E\log V)}$ で行う。
1986年	汎用プッシュ再ラベル法[4]	${\displaystyle O(V^{2}E)}$	プリフロー（頂点群で超過する可能性のあるフロー関数）を使うアルゴリズム。正の超過のある頂点（グラフ内のアクティブな頂点）がある限り、アルゴリズムを繰り返す。プッシュ操作によって残余枝でのフローを増加させ、頂点における高さ関数でどの残余枝にプッシュを行うかを制御する。高さ関数は再ラベル操作で変更される。これらを正しく定義することで、最終的なフロー関数が最大フローを導き出す。
1986年	FIFO式頂点選択規則付きプッシュ再ラベル法[4]	${\displaystyle O(V^{3})}$	最も以前に活性化された頂点を常に選択するプッシュ再ラベル法。
1986年	動的木を使ったプッシュ再ラベル法[4]	${\displaystyle O(VE\log(V^{2}/E))}$	height 関数について残余グラフの限定的な木構造を構築し、多層的プッシュ操作を行う。
1994年	KRT (King, Rao, Tarjan) 法[5]	${\displaystyle O(EV\log _{E/V\log V}V)}$
1998年	バイナリブロッキングフロー法[6]	${\displaystyle O(E\min(V^{2/3},{\sqrt {E}})\log(V^{2}/E)\log {U})}$	計算量のUはネットワークの最大容量。
2013年	Jim Orlin法 + KRT (King, Rao, Tarjan) 法[7]	${\displaystyle O(VE)}$	Jim Orlin法自体は${\displaystyle O(VE+E^{31/16}\log ^{2}V)}$だが、KRT法を組み合わせることで${\displaystyle O(VE)}$になる。

これら以外にも解法アルゴリズムは多数存在し、参考文献（特に Goldberg and Tarjan 1988）を参照されたい。

脚注・出典

参考文献

• Daniel D. Sleator and Robert E. Tarjan (1983). “A data structure for dynamic trees”. Journal of Computer and System Sciences 26 (3): 362–391. doi:10.1016/0022-0000(83)90006-5. ISSN 0022-0000. http://www.cs.cmu.edu/~sleator/papers/dynamic-trees.pdf. 
• Daniel D. Sleator and Robert E. Tarjan (1985). “Self-adjusting binary search trees”. Journal of the ACM (New York, NY, USA: ACM Press) 32 (3): 652–686. doi:10.1145/3828.3835. ISSN 0004-5411. http://www.cs.cmu.edu/~sleator/papers/self-adjusting.pdf. 
• Andrew V. Goldberg and Robert E. Tarjan (1988). “A new approach to the maximum-flow problem”. Journal of the ACM (New York, NY, USA: ACM Press) 35 (4): 921–940. doi:10.1145/48014.61051. ISSN 0004-5411. http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.91.1599. 
• Joseph Cheriyan and Kurt Mehlhorn (1999). “An analysis of the highest-level selection rule in the preflow-push max-flow algorithm”. Information Processing Letters 69 (5): 239–242. doi:10.1016/S0020-0190(99)00019-8. http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.42.8563. 

表 話 編 歴 数理最適化 • 最適化問題 : メソッド • ヒューリスティック
非線形(無制約)	… 関数　 黄金分割探索 直線探索 ネルダー–ミード法 連続放物線補間（英語版） 勾配法 収束性 信頼領域 ウルフ条件（英語版） 準ニュートン法 BFGS法 ブロイデン法 L-BFGS（英語版） DFP法 対称ランク1法（英語版） その他の求解法 ガウス・ニュートン法 最急降下法 レーベンバーグ・マルカート法 共役勾配法（非線形共役勾配法） 切り捨てニュートン法（英語版） ドッグレッグ法 … ヘッセ行列 最適化におけるニュートン法（英語版）
非線形(制約付き)	一般 バリア関数 ペナルティ関数法（英語版） 微分可能 ラグランジュの未定乗数法 逐次二次計画法 連続線形計画（英語版）
凸最適化	凸縮小化 切除平面法（英語版、デンマーク語版、ドイツ語版、スペイン語版） 簡約勾配法 劣勾配法（英語版） 線型 および 二次 内点法 カチヤンの楕円体法 カーマーカーの投影アルゴリズム ベイズ-交換 単体法 改訂単体法（英語版） 十文字法（英語版） レムケの主ピボット操作法（英語版）
組合せ最適化	系列範例 (Paradigms) 近似アルゴリズム 動的計画法 貪欲法 整数計画問題(分枝限定法 若しくは 分枝カット法) グラフ理論 最小全域木 ベルマン–フォード法 ブルーフカ法 ダイクストラ法 ワーシャル–フロイド法 ジョンソン法（英語版） クラスカル法 最大フロー問題 Dinic法（英語版） エドモンズ・カープ フォード・ファルカーソン プッシュリラベル最大流アルゴリズム（英語版）
メタヒューリスティクス	進化的アルゴリズム（進化戦略） 山登り法 局所探索法 焼きなまし法 タブーサーチ ベイスンホッピング法
カテゴリ（最適化 • アルゴリズム） • ソフトウェア（英語版）