グラフ理論の問題

$s$-$t$ カット $S$ は $s$ を含み $t$ を含まないので、$S=\{s\}\cup X$（$X\subseteq \{a,b,c\}$）と書け、全部で $2^3=8$ 個ある。それぞれの容量を、$S$ から出て $V\setminus S$ に入る辺を拾って計算する。

• $X=\varnothing$: $s\to a,s\to b$ より $4+3=7$
• $X=\{a\}$: $s\to b,a\to b,a\to c$ より $3+2+2=7$
• $X=\{b\}$: $s\to a,b\to c,b\to t$ より $4+1+3=8$
• $X=\{c\}$: $s\to a,s\to b,c\to t$ より $4+3+3=10$
• $X=\{a,b\}$: $a\to c,b\to c,b\to t$ より $2+1+3=6$
• $X=\{a,c\}$: $s\to b,a\to b,c\to t$ より $3+2+3=8$
• $X=\{b,c\}$: $s\to a,b\to t,c\to t$ より $4+3+3=10$
• $X=\{a,b,c\}$: $b\to t,c\to t$ より $3+3=6$

よって最小カットの容量は $6$ である。

（確認）実際に流量 $6$ の流れが存在する。経路ごとに
$$s\to a\to b\to t:2,s\to b\to t:1,s\to a\to c\to t:2,s\to b\to c\to t:1$$
と流すと、各辺の流量は $s\to a:4,s\to b:2,a\to b:2,a\to c:2,b\to c:1,b\to t:3,c\to t:3$ で、どれも容量以下であり、$a,b,c$ で流入量と流出量が等しい（$a$: $4=2+2$、$b$: $2+2=1+3$、$c$: $2+1=3$）。最大流最小カット定理より最大流の値も $6$ であり、上の計算と一致する。

容量 $6$ を与えるカットは $S=\{s,a,b\}$ と $S=\{s,a,b,c\}$ の 2 個なので、答えは $2$ 個である。

$s\in S$, $t\notin S$ より、$S$ は $\{a,b,c\}$ の部分集合 $T$ を用いて $S=\{s\}\cup T$ と書け、全部で $2^3=8$ 通りある。それぞれの容量は、始点が $S$、終点が $V\setminus S$ の辺の容量の和である。

• $S=\{s\}$: $s\to a(4)+s\to b(3)=7$
• $S=\{s,a\}$: $s\to b(3)+a\to b(2)+a\to c(2)=7$
• $S=\{s,b\}$: $s\to a(4)+b\to c(1)+b\to t(3)=8$
• $S=\{s,c\}$: $s\to a(4)+s\to b(3)+c\to t(3)=10$
• $S=\{s,a,b\}$: $a\to c(2)+b\to c(1)+b\to t(3)=6$
• $S=\{s,a,c\}$: $s\to b(3)+a\to b(2)+c\to t(3)=8$
• $S=\{s,b,c\}$: $s\to a(4)+b\to t(3)+c\to t(3)=10$
• $S=\{s,a,b,c\}$: $b\to t(3)+c\to t(3)=6$

最小の容量は 6 で、これを与えるのは $S=\{s,a,b\}$ と $S=\{s,a,b,c\}$ の 2 個。

検算: 流量 $s\to a:4,s\to b:2,a\to b:2,a\to c:2,b\to c:1,b\to t:3,c\to t:3$ は各頂点で保存則を満たし（$a$: 流入4=流出4、$b$: 流入4=流出4、$c$: 流入3=流出3）、各辺の容量内で、流量の値は $6$。最大フロー最小カット定理より最小カット容量は 6 で一致する。