グラフ理論の問題

1. 最大流を求める。
次の流れ $f$ を考える。
$$f(s\to a)=3,f(s\to b)=2,f(a\to b)=1,f(a\to c)=2,f(b\to c)=1,f(b\to d)=2,$$
$$f(c\to t)=3,f(d\to e)=2,f(e\to t)=2,f(c\to d)=0,f(c\to e)=0.$$
各辺で $0\le f\le$ 容量であり、流量保存も成り立つ（$a$: 入 $3$、出 $1+2=3$。$b$: 入 $2+1=3$、出 $1+2=3$。$c$: 入 $2+1=3$、出 $3$。$d$: 入 $2$、出 $2$。$e$: 入 $2$、出 $2$）。流量は $3+2=5$ である。一方、カット $S=\{s\}$ の容量は $3+2=5$ なので、最大流最小カット定理より最大流量も最小カット容量も $5$ であり、$f$ は最大流である。

2. 最小カットの特徴づけ。
任意の $s$-$t$ カット $S$ に対して、流量保存を $S$ 内の頂点について足し合わせると
$$5=\sum _{u\in S,v\notin S}f(u\to v)-\sum _{u\notin S,v\in S}f(u\to v)\le \sum _{u\in S,v\notin S}c(u\to v)=\mathrm{cap}(S).$$
したがって $\mathrm{cap}(S)=5$（最小）となるのは、次の 2 条件がともに成り立つときに限る。
- (i) $S$ から外へ出る辺はすべて飽和している（$f=c$）。
- (ii) 外から $S$ へ入る辺の流量はすべて $0$ である。

3. 条件を書き下す。
(i) 飽和していない辺は $c\to d$, $c\to e$（ともに流量 $0$、容量 $1$）だけなので、「$c\in S$ ならば $d\in S$ かつ $e\in S$」。
(ii) 流量が正の辺 $u\to v$ について「$v\in S$ ならば $u\in S$」。$t\notin S$ なので $c\to t$, $e\to t$ からは条件が出ず、残りから
$$a\Rightarrow s,b\Rightarrow s,a,c\Rightarrow a,b,d\Rightarrow b,e\Rightarrow d$$
を得る（$x\Rightarrow y$ は「$x\in S$ ならば $y\in S$」）。$c$ については (i) と合わせて $c\Rightarrow a,b,d,e$ となる。

4. 数え上げ。
$a,b,d,e$ については $e\Rightarrow d\Rightarrow b\Rightarrow a$ という鎖になっているので、$S\cap \{a,b,d,e\}$ は $\varnothing ,\{a\},\{a,b\},\{a,b,d\},\{a,b,d,e\}$ の 5 通りに限られる。$c\in S$ のときは $a,b,d,e$ がすべて必要なので $\{a,b,c,d,e\}$ の 1 通りである。よって最小カットは
$$\{s\},\{s,a\},\{s,a,b\},\{s,a,b,d\},\{s,a,b,d,e\},\{s,a,b,c,d,e\}$$
の 6 個である。

確認（容量を直接計算する）:
- $\{s\}$: $3+2=5$
- $\{s,a\}$: $2+1+2=5$
- $\{s,a,b\}$: $2+1+2=5$
- $\{s,a,b,d\}$: $a\to c,b\to c,d\to e$ で $2+1+2=5$
- $\{s,a,b,d,e\}$: $2+1+2=5$
- $\{s,a,b,c,d,e\}$: $c\to t,e\to t$ で $3+2=5$

いずれも $5$ である。一方、たとえば $\{s,a,b,c\}$ は $c\to d,c\to e,c\to t,b\to d$ で $1+1+3+2=7$ となり、最小ではない。

答えは $6$ である。

最大フローを求め、その残余グラフから最小カットを数える。

最大フロー。 $s$ から出る辺の容量は $3+2=5$、$t$ に入る辺の容量は $3+2=5$ である。次のフロー $f$ で値 $5$ が実現できる。
- $s\to a:3$, $s\to b:2$, $a\to b:1$, $a\to c:2$, $b\to c:1$, $b\to d:2$, $c\to t:3$, $d\to e:2$, $e\to t:2$
- $c\to d:0$, $c\to e:0$

各頂点で流入と流出が等しいことを確かめる。$a$ は $3=1+2$、$b$ は $2+1=1+2$、$c$ は $2+1=3$、$d$ は $2=2$、$e$ は $2=2$ で成り立つ。したがって最大フロー $=$ 最小カット容量 $=5$ である。

最小カットの条件。 カット $S$ が最小であることは、次の2つが成り立つことと同値である。
- $S$ から出る辺はすべて飽和している。
- $S$ に入る辺のフローは $0$ である。

飽和していない辺は $c\to d$ と $c\to e$ だけで、他はすべて飽和している。フローが正の辺は $s\to a,s\to b,a\to b,a\to c,b\to c,b\to d,c\to t,d\to e,e\to t$ である。

これらから $S\setminus \{s\}\subset \{a,b,c,d,e\}$ について次の条件が得られる。
- $b\in S\Rightarrow a\in S$（辺 $a\to b$ が正のフロー）
- $c\in S\Rightarrow a,b\in S$（辺 $a\to c$, $b\to c$ が正のフロー）
- $d\in S\Rightarrow b\in S$（辺 $b\to d$ が正のフロー）
- $e\in S\Rightarrow d\in S$（辺 $d\to e$ が正のフロー）
- $c\in S\Rightarrow d,e\in S$（辺 $c\to d$, $c\to e$ は飽和していないので $S$ から出られない）

数え上げ。
- $c\notin S$ のとき、$a\ge b\ge d\ge e$ の鎖状の条件になる。$S\setminus \{s\}$ は $\varnothing ,\{a\},\{a,b\},\{a,b,d\},\{a,b,d,e\}$ の $5$ 通りである。
- $c\in S$ のとき、$a,b,d,e$ がすべて必要なので $1$ 通りである。

合計 $6$ 個。

検算。 $S=\{s\}$ は $3+2=5$ である。$S=\{s,a\}$ は $s\to b:2$, $a\to b:1$, $a\to c:2$ で $5$ である。$S=\{s,a,b,c,d,e\}$ は $c\to t:3$, $e\to t:2$ で $5$ である。いずれも $5$ になる。