最大フロー・最小カット定理

1. $N'$ において入口 $v$ から到達可能な頂点全ての集合を $S$ と置きます。 もちろん $v \in S$ であり、また $N'$ には増加道が無いので $w \not\in S$ ですから $K=(S,\ol{S})$ は $N$ のカットになります。
2. $a=xy\in K=(S,\ol{S})$ を任意に取ります。 もし $\Psi'(a) \gt 0$ であれば、$N'$ の中の $v$-$x$ 道と $a=xy$ をつなげば $v$-$y$ 道が作れるので $y \in \ol{S}$ であることに矛盾します。 従って $\Psi'(a) = 0$ でなければなりません。
3. $N'$ の作り方から $\Psi'(a) = \Psi(a) - \varphi(a) + \varphi(a^{-1})$ ですが、フローの条件より $\varphi(a) \leqq \Psi(a)$, $\varphi(a^{-1}) \geqq 0$ ですから、2° により $\varphi(a) = \Psi(a)$ かつ $\varphi(a^{-1}) = 0$ が言えます。 $a^{-1}$ は $(\ol{S}, S)$ の弧ですから、結局
   • $K=(S,\ol{S})$ の全ての弧 $a$ に対して $\varphi(a)=\Psi(a)$
   • $(\ol{S},S)$ の全ての弧 $a$ に対して $\varphi(a)=0$
   であることがわかりました。
4. 3° と Th.5 より ( $\varphi$ の値 ) $= \Psi(K)$ となり、 Th.7 より $\varphi$ は最大フローです。同時に Th.8 も証明できました。(証明終)

最大フロー・最小カットの例

Ex.11（教科書 p.183） $N$ : の最大フローは $\varphi$ :   でした。Th.5 の等号条件をヒントに対応する最小カット $K$ を探すと次の赤い弧たちがそうです。 記号で書くと、$S=\{\,v,x,y,z\,\}$, $\ol{S}=\{\,w\,\}$ として $K=(S,\ol{S})$ になります。 また も最小カットです。こちらは $S=\{\,v,x,y\,\}$, $\ol{S}=\{\,w,z\,\}$ の場合です。