組合せとグラフの理論(塩田)第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 は最小カットとなります。(証明終)