組合せとグラフの理論(塩田)第13回 (3) 最大フロー・最小カット定理

前へ / 戻る / 次へ $\newcommand{\ol}[1]{\overline{#1}}$

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

 そしていよいよ、驚くべき定理です。
Th.8(最大フロー・最小カット定理) $N$ の最大フロー $\varphi$ と最小カット $K=(S,\ol{S})$ は必ず
( $\varphi$ の値 ) $= \Psi(K)$
を満たす。すなわち
( 最大フローの値 ) $=$ ( 最小カットの容量 )
が成り立つ。
 $N'$ を 前回の「残りを表すネットワーク」とし、次の定理と一緒に証明しましょう。
Th.9(前回の Th.11 ネットワーク $N=(D,\Psi)$ のフロー $\varphi$ が最大フローであることと、 $N'$ が増加道を持たないことが同値である。
Th.9 の証明 $\Rightarrow$) は前回示しました。逆に、$N'$ が増加道を含まないと仮定して、$\varphi$ が最大フローであることを導きましょう。
  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 も証明できました。(証明終)
Rem.10 最大フロー $\varphi$ に対しては
( $\varphi$ の値 ) $= \Psi(K)$
を満たすカット $K$ が必ず存在します。 もしそのような $K$ が上手く見つかれば、$N'$ を作らなくても $\varphi$ が最大フローであることが言えます。 比較的小さいグラフで最大フローの手計算をするときにはしばしば有効な手段です。

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

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\,\}$ の場合です。
Rem.12 「Def.1 のカット」は「教科書のカット」のうち極小なものを指しますので、 Th.7, Th.8 は「教科書のカット」の意味でも成立しています。