ネットワークフロー ― グラフを流れるもの
フローネットワーク，最大フロー最小カット定理，Ford-Fulkerson法，Edmonds-Karp，Dinic，二部マッチングへの帰着を体系的に解説する．
1 フローネットワークの定義
定義 1 (フローネットワーク).
フローネットワークとは，有向グラフ ，容量関数 ，ソース ，シンク （）の組 をいう．
定義 2 (フロー).
フローネットワーク 上のフローとは，関数 であって次を満たすものをいう：
容量制約：すべての に対して ．
流量保存則： 以外の各頂点 に対して ．
2 残余グラフと増加路
定義 3 (残余グラフ).
フロー に対する残余グラフ を次で定める：各辺 に対して，
ならば，残余容量 の順辺．
ならば，残余容量 の逆辺．
定義 4 (増加路).
残余グラフ における から への路を増加路（augmenting path）という．増加路 のボトルネック容量は である．
3 カットと最大フロー最小カット定理
定義 5 (カット).
の分割 （，）を-カットという．カットの容量を
と定める．
定理 6 (弱双対性).
任意のフロー と任意の - カット に対して が成り立つ．
証明.
流量保存則を の各頂点について足し合わせると，
□
定理 7 (最大フロー最小カット定理).
以下の 条件は同値である：
は最大フローである．
に - 増加路が存在しない．
ある - カット が存在して ．
証明.
：増加路が存在すればフロー値を増やせるので， は最大でない．： で から到達可能な頂点集合を ， とする．（増加路がないため）なので は - カット． で なら すなわち ． で なら すなわち ．よって
：弱双対性より，任意のフロー に対し なので は最大． □
4 Ford-Fulkerson 法
Ford-Fulkerson 法は，から出発し，で増加路を見つけてフローを増加する操作を繰り返す．
アルゴリズム 1: Ford-Fulkerson 法
Input:
フローネットワーク Output:
最大フロー for all
end for
while 残余グラフ に から への増加路 が存在する
// ボトルネック容量
for all
// に沿ってフロー更新
if
// 順辺
else
// 逆辺
end if
end for
end while
return
注意 8.
容量が有理数ならば Ford-Fulkerson 法は有限回で停止し最大フローを求める．しかし無理数の容量では収束しない例が知られている．また，増加路の選び方によっては整数容量でも非常に遅くなりうる．増加路の探索に BFS を用いる改良版が Edmonds-Karp アルゴリズムである．
5 Edmonds-Karp アルゴリズム
定理 9 (Edmonds-Karp).
増加路を BFS で（辺数最短のものを）選ぶ場合，フローの増加回数は 回以下であり，全体の計算量は となる．
証明.
鍵となる補題は，各頂点 について における からの BFS 距離 がフロー増加のたびに単調非減少であることである．この補題の下で，ボトルネックとなった辺が次に増加路に含まれるまでに が少なくとも 増加することが示される． なので，各辺がボトルネックになる回数は であり，増加路の総数は である． □
6 Dinic のアルゴリズム
Dinic のアルゴリズムは，BFS で層別グラフ（level graph）を構成し，その上でブロッキングフローを求めることを繰り返す．
定義 10 (層別グラフ).
において からの BFS 距離 を計算し， を満たす辺 のみを残したグラフを層別グラフ（level graph） という．
定理 11 (Dinic の計算量).
Dinic のアルゴリズムの計算量は である．
証明.
各フェーズで層別グラフにおけるブロッキングフローを で求められる．フェーズごとに から への BFS 距離が厳密に増加するため，フェーズ数は高々 回である． □
注意 12.
単位容量のネットワーク（すべての容量が ）では Dinic のアルゴリズムは で動作する．これは二部マッチング（後述）に応用される場合に特に重要である．
7 二部マッチングへの帰着
定理 13 (二部マッチングとフロー).
二部グラフ の最大マッチング問題は，以下のフローネットワークの最大フロー問題に帰着される：ソース から の各頂点に容量 の辺を張り， の各頂点からシンク に容量 の辺を張り， の各辺 に （容量 ）の弧を与える．
証明.
整数容量のフローネットワークの最大フローは整数フローとして実現できる（整数性定理）．容量 の各辺に流量 または が対応し， および に接続する辺の容量制約から各頂点は高々 本の辺でしか使われない．よって流量 の辺集合はマッチングに対応し，フロー値はマッチングの辺数に等しい． □
注意 14.
Dinic のアルゴリズムをこのネットワークに適用すると，Hopcroft-Karp アルゴリズムが自然に得られ，計算量は である．この帰着は König の定理の別証明も与える：最大フロー 最小カット（最大フロー最小カット定理）であり，最小カットの容量は最小頂点被覆の大きさに対応するためである．