フローネットワークと実行可能フロー
フローネットワークとは、互いに異なる始点(source) $s$ と終点(sink) $t$ を指定した有限有向グラフ $G=(V,E)$ である。各辺 $e$ には有限かつ非負の容量 $c_e$ が与えられる。端点が同じでも辺はそれぞれ別のものとして扱う。これは平行辺や互いに逆向きの辺がある場合に重要である。
フローとは、元の各辺 $e$ に実数 $f_e$ を割り当てることである。容量制約
\[0\le f_e\le c_e \qquad(e\in E)\]を満たし、$s,t$ 以外のすべての頂点で流入量と流出量が等しいとき、そのフローは実行可能である。
\[\sum_{e:\,\operatorname{head}(e)=v} f_e =\sum_{e:\,\operatorname{tail}(e)=v} f_e \qquad(v\in V\setminus\{s,t\}).\]実行可能フローの値は、始点から出る正味フローとして定義する。
\[|f|=\sum_{e:\,\operatorname{tail}(e)=s} f_e -\sum_{e:\,\operatorname{head}(e)=s} f_e.\]始点と終点以外の全頂点でのフロー保存則を合計すると、これは終点に入る正味フローにも等しい。
\[|f|=\sum_{e:\,\operatorname{head}(e)=t} f_e -\sum_{e:\,\operatorname{tail}(e)=t} f_e.\]したがって、$s$ に入る辺や $t$ から出る辺がある場合、フロー値は $s$ から出るフローや $t$ に入るフローの単純な合計ではない。
残余辺と残余ネットワーク
実行可能フロー $f$ に対して、元の辺 $e=(u,v)$ は、その辺を識別するラベル付きの残余辺を最大2本生じさせる。
- 順方向残余辺 $(u,v,e,+)$ の残余容量は $c_e-f_e$ である。これは $e$ に沿ってさらに送れるフロー量を表す。
- 逆方向残余辺 $(v,u,e,-)$ の残余容量は $f_e$ である。これは $e$ 上の既存フローを減らして取り消したり、逆向きに戻したりできる量を表す。
残余容量が正の辺だけを残余ネットワークで利用できる。残余辺を元の辺と混同してはならない。特に $e=(u,v)$ に属する逆方向残余辺は、反対向き $v\to u$ の元の辺とは別物である。元の辺が両方向に存在する場合、それぞれの元の辺が独立した順方向・逆方向残余辺を生じさせる。
すべての実行可能フローを上から抑えるカット
$s$–$t$ カットとは、$V=S\mathbin{\dot\cup}T$、$s\in S$、$t\in T$ を満たす分割である。カット容量は、$S$ から $T$ に向かう元の辺の容量の総和とする。
\[c(S,T)=\sum_{e=(u,v)\in E:\,u\in S,\ v\in T}c_e.\]任意の実行可能フローについて、$S$ に属する頂点の正味流出量を合計すると
\[|f|=\sum_{e=(u,v)\in E:\,u\in S,\ v\in T}f_e -\sum_{e=(u,v)\in E:\,u\in T,\ v\in S}f_e \le c(S,T)\]となる。したがって、すべての実行可能フローの値は、すべての $s$–$t$ カット容量以下である。
増加路
| 増加路とは、正の残余容量を持つ残余辺だけを使って残余ネットワーク内を $s$ から $t$ まで進む路である。そのボトルネック容量は、路上にある残余辺の残余容量の最小値である。この最小値を $\Delta$ としてフローを増加させる。路に含まれる順方向残余辺が元の辺 $e$ に対応するなら $f_e$ を $f_e+\Delta$ にし、逆方向残余辺なら $f_e$ を $f_e-\Delta$ にする。得られるフローは各辺の容量制約と中間頂点でのフロー保存則を保ち、値は $ | f | +\Delta$ となる。 |
実行可能フローが最大フローであるための必要十分条件は、そのフローの残余ネットワークに $s$ から $t$ への増加路が存在しないことである。これは元のグラフではなく、現在のフローに対応する残余ネットワークについての条件である。増加路があれば、その正のボトルネック容量だけフローを増やし、より大きな実行可能フローを作れる。逆に増加路がない場合、正の残余容量の辺をたどって $s$ から到達できる頂点の集合が $s$–$t$ カットを定める。このカットを外向きに横切る元の辺は容量まで使われ、逆向きに横切る辺にはフローが流れていない。したがってフロー値はカット容量に等しく、それより大きいフローは存在しない。
この条件は最適性を特徴づけるが、増加路の選び方を問わず有限回で終了することを保証するものではない。ゼロフローから始め、容量が整数なら、フォード・ファルカーソン法の各増加後もフローは整数値を保ち、整数であるフロー値が毎回少なくとも1増える。フロー値は始点から出る有限な総容量で上から抑えられるため、アルゴリズムは終了する。有理数容量も共通分母を掛けて整数容量にできるので同じ保証がある。一方、任意の実数容量では、経路の選び方によって最大フローに有限回で到達せず、増加が無限に続くことがある。