グラフ理論の問題

フォード・ファルカーソン法で、残余ネットワークに $s$ から $t$ への有向道（増加道）がある限り、その道に沿って流せるだけ流します。

1 本目の増加道 $s\to u\to t$：残余容量は $\min (6,4)=4$ なので $4$ 流します。残余容量は $s\to u$ が $2$、$u\to t$ が $0$ になり、逆向きの辺 $u\to s$ に $4$、$t\to u$ に $4$ ができます。流量の合計は $4$ です。

2 本目の増加道 $s\to v\to t$：残余容量は $\min (2,5)=2$ なので $2$ 流します。残余容量は $s\to v$ が $0$、$v\to t$ が $3$ になります。流量の合計は $4+2=6$ です。

3 本目の増加道 $s\to u\to v\to t$：残余容量は $\min (2,1,3)=1$ なので $1$ 流します。残余容量は $s\to u$ が $1$、$u\to v$ が $0$、$v\to t$ が $2$ になります。流量の合計は $6+1=7$ です。

増加道がないことの確認：このときの残余ネットワークで $s$ から出られる辺は $s\to u$（残余容量 $1$）だけです（$s\to v$ は $0$）。$u$ から出られる辺は逆向きの辺 $u\to s$ だけで、$u\to v$ と $u\to t$ はどちらも残余容量が $0$ です。よって $s$ から到達できる頂点の集合は $S=\{s,u\}$ で、$t$ には到達できません。したがって増加道はもうありません。

得られたフローは
$$s\to u:5,s\to v:2,u\to v:1,u\to t:4,v\to t:3$$
です。どの辺も容量を超えていません。また $u$ では流入 $5$ に対して流出 $1+4=5$、$v$ では流入 $2+1=3$ に対して流出 $3$ なので、流量保存も成り立っています。このフローの値は $7$ です。

カットで最大であることを確かめる：$S=\{s,u\}$ から外へ出る辺は $s\to v$、$u\to v$、$u\to t$ の 3 本です。よってカットの容量は
$$c(S)=2+1+4=7$$
です。どのフローの値もどのカットの容量も超えないので、フローの値は $7$ 以下です。値 $7$ のフローが実際にあるので、最大流の値は $7$ です（最大流最小カット定理）。

参考までに、ほかのカットの容量も調べておきます。$\{s\}$ は $6+2=8$、$\{s,v\}$ は $6+5=11$、$\{s,u,v\}$ は $4+5=9$ で、いずれも $7$ より大きくなります。

最小カットを求める。カット $\{s\}$ の容量は $6+2=8$。カット $\{s,u\}$ の容量は $s\to v$ の $2$、$u\to v$ の $1$、$u\to t$ の $4$ の合計で $7$。カット $\{s,v\}$ の容量は $s\to u$ の $6$ と $v\to t$ の $5$ の合計で $11$。カット $\{s,u,v\}$ の容量は $u\to t$ の $4$ と $v\to t$ の $5$ の合計で $9$。最小カットは $7$ である。

次に流量 $7$ の流れを構成する。$s\to u\to t$ に $4$、$s\to u\to v\to t$ に $1$、$s\to v\to t$ に $2$ を流す。$s\to u$ は $4+1=5\le 6$、$u\to v$ は $1\le 1$、$v\to t$ は $1+2=3\le 5$ で、容量制約を満たす。総流量は $4+1+2=7$ である。

最大流最小カット定理より、最大流の値は $7$ である。