組合せとグラフの理論（塩田）第13回 (2) フローの値とカットの容量の関係
前へ / 戻る / 次へ
$\newcommand{\ol}[1]{\overline{#1}}$
フローの値 $\leqq$ カットの容量
フローにカットがどう関わっているかという最初の定理は
Th.5 $N$ の任意のフロー $\varphi$ と任意のカット $K=(S,\ol{S})$ に対し、
( $\varphi$ の値 ) $\leqq \Psi(K)$
が成り立つ。しかも、ここで等号が成立するのは、
- $K=(S,\ol{S})$ の全ての弧 $a$ に対して $\varphi(a)=\Psi(a)$
- $(\ol{S},S)$ の全ての弧 $a$ に対して $\varphi(a)=0$
が成り立つときに限る。
教科書では明らかなように書いてありますが、ちゃんと示しましょう。
Lemma 6 $N$ の任意のフロー $\varphi$ と任意のカット $K=(S,\ol{S})$ に対し、
( $\varphi$ の値 ) $=\varphi((S,\ol{S}))-\varphi((\ol{S},S))$
が成り立つ。
証明 $x \in S$ から出る弧は、$S$ の頂点に至るものと $\ol{S}$ の頂点に至るものに分けられます。従って
$\dps{\mbox{outdeg}(\varphi,x)=\sum_{a=xy,\, y \in S}\varphi(a)+\sum_{a=xy,\, y \in \ol{S}}\varphi(a)}$
この式を全ての $x \in S$ について加えると
$\dps{\sum_{x \in S}\mbox{outdeg}(\varphi,x)=\sum_{a=xy,\, x,y \in S}\varphi(a)+\sum_{a=xy,\, x \in S,\,y \in \ol{S}}\varphi(a)}$
右辺の第 2 項は $\varphi((S,\ol{S}))$ のことですから
$\dps{\sum_{x \in S}\mbox{outdeg}(\varphi,x)=\sum_{a=xy,\, x,y \in S}\varphi(a)+\varphi((S,\ol{S}))}$
となります。向きを逆にして考えると
$\dps{\sum_{x \in S}\mbox{indeg}(\varphi,x)=\sum_{a=yx,\, x,y \in S}\varphi(a)+\varphi((\ol{S},S))}$
この 2 つの式の右辺第 1 項は同じものですから、片々引くと
$\dps{\sum_{x \in S}\left( \mbox{outdeg}(\varphi,x)-\mbox{indeg}(\varphi,x)\right)
=\varphi((S,\ol{S}))-\varphi((\ol{S},S))}$
入口 $v$ 以外の頂点では $\varphi$ の出次数と入次数が釣り合っていますので
左辺 $= \mbox{outdeg}(\varphi,v)-\mbox{indeg}(\varphi,v) =$ ( $\varphi$ の値 )
(証明終)
Th.5 の証明 フローの条件から、各弧 $a$ について $\varphi(a) \leqq \Psi(a)$ が成り立つので
$\varphi((S,\ol{S}))=\varphi(K) \leqq \Psi(K)$
また $\varphi(a) \geqq 0$ が成り立つので
$\varphi((\ol{S},S)) \geqq 0$
従って
L'a 6 により
( フロー $\varphi$ の値 ) $=\varphi((S,\ol{S}))-\varphi((\ol{S},S)) \leqq \Psi(K)$
等号成立の条件は以上の議論よりわかります。(証明終)
最大フローの十分条件
Th.7 $N$ の或るフロー $\varphi$ と或るカット $K=(S,\ol{S})$ が
( $\varphi$ の値 ) $= \Psi(K)$
を満たせば、$\varphi$ は最大フロー、$K$ は最小カットである。
証明 最大フローのひとつを $\varphi^{\ast}$ 、最小カットのひとつを $K^{\ast}$ とすると、
- $\varphi^{\ast}$ は最大フローゆえ ( $\varphi$ の値 ) $\leqq$ ( $\varphi^{\ast}$ の値 )
- $K^{\ast}$ は最小カットゆえ $\Psi(K^{\ast}) \leqq \Psi(K)$
- Th.5 より ( $\varphi^{\ast}$ の値 ) $\leqq \Psi(K^{\ast})$
これらと仮定をつなぐと、
( $\varphi$ の値 ) $\leqq$ ( $\varphi^{\ast}$ の値 ) $\leqq \Psi(K^{\ast}) \leqq \Psi(K) = $ ( $\varphi$ の値 )
従って全て等号が成り立って、$\varphi$ は最大フロー、$K$ は最小カットとなります。(証明終)