9.3. フローの基礎的な性質

最大フロー問題に取り掛かる前に、フローに関する簡単な観察を証明しよう:

命題 9.3.1

多重有向グラフ $D = (V, A, ψ)$ 、入口 $s \in V$ 、出口 $t \in V$ 、容量関数 $c : A \to N$ から構成されるネットワークを $N$ とする。 $N$ 上のフローを $f : A \to N$ とする。このとき次の等式が成り立つ:

∣ f ∣ = f^{+} (s) - f^{-} (s) = f^{-} (t) - f^{+} (t)

[証明] 次の等式が成り立つ:

v \in V \sum f^{+} (v) = = a \in A \sum v \in V \sum a \in A; a の始点は v \sum f (a) (∵ f^{+} (x) の定義) = a \in A \sum f (a)

[この等式は有名な性質 $v \in V \sum de g^{+} v = ∣ A ∣$ の一般化と言える。] 同様に $v \in V \sum f^{-} (v) = a \in A \sum f (a)$ も成り立つ。ここから次の等式を得る:

v \in V \sum (f^{-} (v) - f^{+} (v)) = = a \in A \sum f (a) v \in V \sum f^{-} (v) - = a \in A \sum f (a) v \in V \sum f^{+} (v) = 0 (1)

一方で、フローの保存制約からは任意の $v \in V ∖ {s, t}$ に対して $f^{-} (v) = f^{+} (v)$ が成り立つと分かる。言い換えれば $f^{-} (v) - f^{+} (v) = 0$ だから、和 $v \in V \sum (f^{-} (v) - f^{+} (v))$ で足されている項は $v = s$ と $v = t$ に対応する項を除いて全て $0$ だと分かる。よって、この和はその二つの項の和に等しい:

v \in V \sum (f^{-} (v) - f^{+} (v)) = (f^{-} (s) - f^{+} (s)) + (f^{-} (t) - f^{+} (t))

これと式 $(1)$ より次の等式を得る:

(f^{-} (s) - f^{+} (s)) + (f^{-} (t) - f^{+} (t)) = 0

よって $∣ f ∣$ の定義より次の等式が分かる:

f^{-} (t) - f^{+} (t) = - (f^{-} (s) - f^{+} (s)) = f^{+} (s) - f^{-} (s) = ∣ f ∣

以上で命題 9.3.1 は証明された。□

命題 9.3.2

多重有向グラフ $D = (V, A, ψ)$ 、入口 $s \in V$ 、出口 $t \in V$ 、容量関数 $c : A \to N$ から構成されるネットワークを $N$ とする。 $f : A \to N$ を $N$ 上のフロー、 $S$ を $V$ の部分集合とする。このとき:

次の等式が成り立つ:

$f (S, \overline{S}) - f (\overline{S}, S) = v \in S \sum (f^{+} (v) - f^{-} (v))$

[定義 9.1.5 で定めたように、 $f (P, Q)$ は $a \in [P, Q] \sum f (a)$ を意味する。]
$s \in S$ かつ $t \in / S$ なら、次の等式が成り立つ:

$∣ f ∣ = f (S, \overline{S}) - f (\overline{S}, S)$
$s \in S$ かつ $t \in / S$ なら、次の不等式が成り立つ:

$∣ f ∣ \leq c (S, \overline{S})$
$s \in S$ かつ $t \in / S$ なら、 $∣ f ∣ = c (S, \overline{S})$ が成り立つのは次の二つの条件が満たされるとき、かつそのときに限る:

$1. 任意の 2. 任意の a \in [\overline{S}, S] に対して f (a) = 0 a \in [S, \overline{S}] に対して f (a) = c (a)$

[証明] 最初に、以前に言及した「送金スキーム用のネットワーク」の例を使って示すべき命題を言い換えるとどうなるかを示す。 $S$ を特定の国にある銀行口座全体の集合と考えると、 $f (S, \overline{S})$ は送金処理における国 $S$ の「輸出額」 ( $S$ から出ていく資金) であり、 $f (\overline{S}, S)$ は送金処理における国 $S$ の「輸入額」( $S$ に入ってくる資金) である。命題 9.3.2 (a) は、 $S$ の「純輸出額」 ( $S$ の輸出から $S$ の輸入を引いた額) が $S$ 国内の銀行の出流量から入流量を引いた値の和に等しいと主張する。これは直感的にも明らかだろう (特に、純輸出額の計算において $S$ 国内の銀行口座間の資金移動は打ち消されて $0$ になる)。(b) は、 $S$ が入口 $s$ を含み出口 $t$ を含まない (資金の移動元が国内にあり、移動先が国外にある) とき、移動する資金の総額は $S$ の純輸出額に等しいと主張する。(c) は、同様の仮定の下で、移動する資金の総額は $S$ の「輸出能力」 $c (S, \overline{S})$ (「輸出弧」 $a \in [S, \overline{S}]$ の容量の和) 以下だと主張する。(d) は、この不等式で等号が成り立つ (移動する資金の総額が $S$ の輸出能力に等しい) とき、「輸入弧」 $a \in [\overline{S}, S]$ は使われておらず ( $S$ に輸入される資金は存在せず)、「輸出弧」 $a \in [S, \overline{S}]$ は容量の限界まで使われていると主張する。

これで命題 9.3.2 の主張が納得できたことを願う。ただ、証明しないまま次に進むのは気持ちが良くないので、以下に数学的に厳密な証明を示す (和の変形はこれまでに十分経験してきたと思うので、他の証明よりは簡潔にしてある)。

(a): 次の変形から従う:

v \in S \sum (f^{+} (v) - f^{-} (v)) = = f (S, V) [なぜ？] v \in S \sum f^{+} (v) - = f (V, S) [なぜ？] v \in S \sum f^{-} (v) = = f (S, S) + f (S, \overline{S}) (∵ V は共通要素を持たない 二つの集合 S, \overline{S} の和集合) f (S, V) - = f (S, S) + f (\overline{S}, S) (∵ V は共通要素を持たない 二つの集合 S, \overline{S} の和集合) f (V, S) = f (S, S) + f (S, \overline{S}) - (f (S, S) + f (\overline{S}, S)) = f (S, \overline{S}) - f (\overline{S}, S)

(b): $t \in / S$ より $S ∖ {s} \subseteq V ∖ {s, t}$ が成り立つので、(a) より次を得る:

f (S, \overline{S}) - f (\overline{S}, S) = v \in S \sum (f^{+} (v) - f^{-} (v)) = = ∣ f ∣ (∵ ∣ f ∣ の定義) (f^{+} (s) - f^{-} (s)) + v \in S ∖ {s} \sum = 0 (∵ フローの保存制約と v \in S ∖ {s} \subseteq V ∖ {s, t}) (f^{+} (v) - f^{-} (v)) (∵ s \in S) = ∣ f ∣

以上で (b) は証明された。

(c): フローの容量制約より任意の弧 $a \in A$ に対して $f (a) \leq c (a)$ が成り立つ。この不等式を全ての $a \in [S, \overline{S}]$ にわたって足し上げると $f (S, \overline{S}) \leq c (S, \overline{S})$ を得る。フローの容量制約からは $f (a) \geq 0$ も分かる。この不等式を全ての $a \in [\overline{S}, S]$ にわたって足し上げると $f (\overline{S}, S) \geq 0$ を得る。よって (b) から次の等式が分かる:

∣ f ∣ = \leq c (S, \overline{S}) f (S, \overline{S}) - \geq 0 f (\overline{S}, S) \leq c (S, \overline{S})

以上で (c) は証明された。

(d): (c) で等号が成り立つケースを考える必要がある。ただ、(c) の証明を思い出してほしい: 不等式 $∣ f ∣ \leq c (S, \overline{S})$ は、全ての弧 $a \in [S, \overline{S}]$ にわたって不等式 $f (a) \leq c (a)$ を足し上げることで得られていた。よって不等式 $∣ f ∣ \leq c (S, \overline{S})$ における等号の成立は、この不等式に関係する全ての不等式 ── 全ての弧 $a \in [S, \overline{S}]$ に対する $f (a) \leq c (a)$ と、全ての弧 $a \in [\overline{S}, S]$ に対する $f (a) \geq 0$ ── における等号の成立と同値である。言い換えれば、次の二つの条件を満たすことが等号成立のための必要十分条件である:

任意の 任意の a \in [\overline{S}, S] に対して f (a) = 0 a \in [S, \overline{S}] に対して f (a) = c (a)

以上で (d) は証明された。□