グラフ理論の問題

手順 1：フォード・ファルカーソン法で流量を増やす。

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

• 増加道 $s\to u\to t$：残余容量は $\min (3,2)=2$。流量 $2$ を流す。残余容量は $s\to u$ が $1$、$u\to t$ が $0$ になる。
• 増加道 $s\to v\to t$：残余容量は $\min (2,4)=2$。流量 $2$ を流す。残余容量は $s\to v$ が $0$、$v\to t$ が $2$ になる。
• 増加道 $s\to u\to v\to t$：残余容量は $\min (1,1,2)=1$。流量 $1$ を流す。残余容量は $s\to u$ が $0$、$u\to v$ が $0$、$v\to t$ が $1$ になる。

この時点で $s$ から出る辺 $s\to u,s\to v$ の残余容量はどちらも $0$ で、$s$ に入る辺はもともとないので逆向きの残余辺も $s$ から出ない。よって増加道はもうない。得られたフローの値は $2+2+1=5$ である。

手順 2：カットの容量をすべて計算する。

$s\in S,t\notin S$ なので、$S$ は $u,v$ を入れるかどうかで $2^2=4$ 通りある。$S$ から外へ出る辺の容量を足す（外から $S$ に入る辺は数えない）。

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

手順 3：最大であることの確認と最小カットの数え上げ。

どのフローの値もどのカットの容量も超えないので、フローの値は $5$ 以下である。手順 1 で値 $5$ のフローが得られたので、最大流の値は $5$ である。また最小カットの容量も $5$ であり（最大流最小カット定理）、容量 $5$ のカットは $S=\{s\}$ と $S=\{s,u\}$ の $2$ 個である。

よって答えは $(5,2)$。

最大流：s→u:3, s→v:2, u→v:1, u→t:2, v→t:4。
sから出る容量の合計は 3+2=5。tに入る容量の合計は 2+4=6。
流れの例：s→u に3、s→v に2を流す。u→t に2、u→v に1を流す。v には 2+1=3 が入り、v→t に3を流す。t への流入は 2+3=5。各辺は容量以内なので、最大流は少なくとも5。

カット：s∈S, t∉S で、u,v の入れ方は4通り。
1. S={s}：c = 3+2 = 5
2. S={s,u}：s→v:2, u→v:1, u→t:2 で c = 5
3. S={s,v}：s→u:3, v→t:4 で c = 7
4. S={s,u,v}：u→t:2, v→t:4 で c = 6

最小カット容量は5で、最大流最小カット定理より最大流の値は5。
容量5のカットは S={s} と S={s,u} の2個。

検算：S={s,u} のカットで、s→v:2, u→v:1, u→t:2 はいずれも上の流れで飽和している（2, 1, 2）。S={s} でも s→u:3, s→v:2 が飽和している。よって整合する。

答え：(5, 2)