残余ネットワーク・増加道

フロー $f$ に対し、各辺 $e=(x,y)\in E$ から 2 種類の残余辺を作る。

• $f(e)<c(e)$ のとき、$x$ から $y$ への順方向の残余辺 $e^+$。残余容量は $c(e)-f(e)$。
• $f(e)>0$ のとき、$y$ から $x$ への逆方向の残余辺 $e^-$。残余容量は $f(e)$。

残余辺の全体を $f$ の残余ネットワーク $R_f$ という。相異なる頂点の列 $s=v_0,v_1,\dots,v_k=t$ と、$v_{i-1}$ から $v_i$ への残余辺 $a_i$ の列を $f$-増加道といい、$a_i$ の残余容量の最小値 $\varepsilon>0$ をその残余容量という。増加道に沿って $f$ を増加するとは、$a_i=e^+$ である辺 $e$ で $f(e)$ を $\varepsilon$ 増やし、$a_i=e^-$ である辺 $e$ で $f(e)$ を $\varepsilon$ 減らすことをいう。