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

フローの値 $\leqq$ カットの容量

　フローにカットがどう関わっているかという最初の定理は 　教科書では明らかなように書いてありますが、ちゃんと示しましょう。 証明　$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)$ 等号成立の条件は以上の議論よりわかります。(証明終)

最大フローの十分条件

証明　最大フローのひとつを $\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$ は最小カットとなります。(証明終)

前へ / 戻る / 次へ