グラフ理論の問題

手順1：フォード・ファルカーソン法で増加道を探す。

はじめはすべての辺の流量を $0$ とし、残余ネットワークで $s$ から $t$ への道を探して、道の上の残余容量の最小値だけ流す。

• 増加道 $s\to a\to t$：残余容量は $3,2$ なので、最小値 $2$ だけ流す。残余容量は $s\to a:1$、$a\to t:0$ になる。
• 増加道 $s\to b\to t$：残余容量は $2,3$ なので、最小値 $2$ だけ流す。残余容量は $s\to b:0$、$b\to t:1$ になる。
• 増加道 $s\to a\to b\to t$：残余容量は $1,1,1$ なので、$1$ だけ流す。残余容量は $s\to a:0$、$a\to b:0$、$b\to t:0$ になる。

このとき $s$ から出る辺 $s\to a$、$s\to b$ の残余容量はどちらも $0$ である。$s$ に入る辺はもとのネットワークにないので逆向きの残余辺も $s$ からは出ない。したがって残余ネットワークで $s$ から先へ進めず、増加道はもう存在しない。得られたフローの値は
$$2+2+1=5$$
である。

手順2：同じ容量のカットで最大性を確かめ、最小カットを数える。

$s\in S$、$t\notin S$ を満たす $S$ は、$a,b$ をそれぞれ $S$ に入れるか入れないかで $2\times 2=4$ 個ある。それぞれの容量を、$S$ から $S$ の外へ向かう辺の容量の和として計算する。

• $S=\{s\}$：$s\to a,s\to b$ なので $c(S)=3+2=5$
• $S=\{s,a\}$：$s\to b,a\to b,a\to t$ なので $c(S)=2+1+2=5$
• $S=\{s,b\}$：$s\to a,b\to t$ なので $c(S)=3+3=6$（$a\to b$ は $S$ に入る向きなので数えない）
• $S=\{s,a,b\}$：$a\to t,b\to t$ なので $c(S)=2+3=5$

どのフローの値もどのカットの容量も超えないので、フローの値は $5$ 以下である。手順1で値 $5$ のフローが得られたから、最大流の値は $5$ である（最大流最小カット定理のとおり、最小カットの容量も $5$ となる）。

容量が最小値 $5$ になるカットは $\{s\},\{s,a\},\{s,a,b\}$ の $3$ 個である。

よって答えは $(5,3)$ である。

最大流最小カット定理より、最大流の値は最小カットの容量に等しい。

$s\in S$、$t\notin S$ を満たす $S$ は $\{a,b\}$ の部分集合 4 通りに $s$ を加えたものである。それぞれの容量を計算する。
- $S=\{s\}$: $s\to a$ と $s\to b$ が出ていくので $3+2=5$。
- $S=\{s,a\}$: $s\to b$、$a\to b$、$a\to t$ が出ていくので $2+1+2=5$。
- $S=\{s,b\}$: $s\to a$ と $b\to t$ が出ていくので $3+3=6$。
- $S=\{s,a,b\}$: $a\to t$ と $b\to t$ が出ていくので $2+3=5$。

最小容量は 5 で、それを与えるカットは 3 個である。

検算として、容量 5 の流れが実際に作れることを確かめる。$s\to a$ に 3、$s\to b$ に 2 を流す。$a$ からは $a\to t$ に 2、$a\to b$ に 1 を流す。$b$ には $2+1=3$ が入り、$b\to t$ に 3 を流す。どの辺も容量以内で、$t$ に入る流量は $2+3=5$ となる。よって最大流は 5 である。

答えは $(5,3)$。