グラフ理論の問題

最大流の値 次の流れ $f$ を考える（括弧内は流量）。
$$e_1(7),e_2(6),e_3(5),e_4(3),e_5(4),e_6(2),e_7(1),e_8(3),e_9(3),e_{10}(2),e_{11}(5),e_{12}(8),e_{13}(5)$$
どの辺も容量以下で、各中間頂点で流入量と流出量が等しい（$a_1:7=3+4$、$a_2:6=2+1+3$、$a_3:5=3+2$、$b_1:3+2=5$、$b_2:4+1+3=8$、$b_3:3+2=5$）。値は $7+6+5=18$ である。

一方、$S_1=\{s,a_1,a_3\}$ とするカット $(S_1,V\setminus S_1)$ の容量は、$S_1$ から出る辺 $e_2,e_4,e_5,e_9,e_{10}$ の容量の和 $6+3+4+3+2=18$ である。最大流最小カット定理より、最大流の値は $18$、最小カットの容量も $18$ である。

すべての最小カットを求める 最大流 $f$ に関する残余ネットワーク（流量が容量未満の辺は順向きに、流量が正の辺は逆向きに通れる）を考える。$(S,T)$ が最小カットのとき、$f$ の値 $=$ カットの容量なので、$S\to T$ の辺はすべて飽和し、$T\to S$ の辺の流量はすべて $0$ である。したがって残余ネットワークでは $S$ から $T$ へ向かう辺が 1 本もなく、
- $s$ から残余ネットワークでたどり着ける頂点はすべて $S$ に入る
- 残余ネットワークで $t$ にたどり着ける頂点はすべて $T$ に入る

残余ネットワークで $s$ から進めるのは $s\to a_1$（残り $1$）と $s\to a_3$（残り $2$）だけで、$a_1$ から出る $e_4,e_5$、$a_3$ から出る $e_9,e_{10}$ はすべて飽和しており、逆向きの辺は $s$ に戻るだけである。よって $s$ から到達できる頂点は $\{s,a_1,a_3\}$。

$t$ に入る残余辺は $b_2\to t$（残り $1$）と $b_3\to t$（残り $1$）だけ（$e_{11}$ は飽和）。$b_2$ に入る辺 $e_5,e_7,e_9$ と $b_3$ に入る辺 $e_8,e_{10}$ はすべて飽和しているので、$t$ に到達できる頂点は $\{b_2,b_3,t\}$。

よって最小カットは $\{s,a_1,a_3\}\subseteq S$、$b_2,b_3,t\notin S$ を満たし、残りの $a_2,b_1$ を入れるかどうかの 4 通りを調べればよい。
- $S=\{s,a_1,a_3\}$：容量 $18$（上で計算）
- $S=\{s,a_1,a_2,a_3\}$：$e_4,e_5,e_6,e_7,e_8,e_9,e_{10}$ で $3+4+4+1+3+3+2=20$
- $S=\{s,a_1,a_3,b_1\}$：$e_2,e_5,e_9,e_{10},e_{11}$ で $6+4+3+2+5=20$
- $S=\{s,a_1,a_2,a_3,b_1\}$：$e_5,e_7,e_8,e_9,e_{10},e_{11}$ で $4+1+3+3+2+5=18$

したがって最小カットはちょうど 2 つで、そのカット辺の集合は $\{e_2,e_4,e_5,e_9,e_{10}\}$ と $\{e_5,e_7,e_8,e_9,e_{10},e_{11}\}$ である。

容量を 1 増やしたときの変化 辺 $e_i$ の容量を $1$ 増やすと、$e_i$ を含むカットの容量は $1$ 増え、含まないカットの容量は変わらない。
- $e_i$ が 2 つの最小カットの両方に含まれるとき：容量 $18$ のカットはなくなり、ほかのカットは元から容量が $19$ 以上（容量はすべて整数で、$18$ のカットは上の 2 つだけ）なので、新しい最小カットの容量は $19$ となり、最大流は $19$ に増える。
- $e_i$ を含まない最小カットがあるとき：そのカットの容量は $18$ のままなので、最大流は $18$ のまま増えない。

両方の最小カットに共通する辺は $e_5,e_9,e_{10}$ である。よって求める番号の集合は $\{5,9,10\}$ である。

まず最大流を求める。上界: $b_1$ への流入は容量 $3+4=7$ だが $b_1\to t$ は 5、$b_2$ への流入は $4+1+3=8$、$b_3$ への流入は $3+2=5$ なので、$t$ への流れは高々 $5+8+5=18$。
18 を達成する流れ: $s\to a_1$: 7、$s\to a_2$: 6、$s\to a_3$: 5。$a_1\to b_1$: 3、$a_1\to b_2$: 4。$a_2\to b_1$: 2、$a_2\to b_2$: 1、$a_2\to b_3$: 3。$a_3\to b_2$: 3、$a_3\to b_3$: 2。$b_1\to t$: 5、$b_2\to t$: 8、$b_3\to t$: 5。保存則と容量制約を満たし、総流量は 18。最大流の値は 18。

容量を 1 増やして最大流が増える辺は、すべての最小カットに含まれる辺である。
残余グラフで $s$ から到達できる頂点は $s\to a_1$（残 1）、$s\to a_3$（残 2）より $\{s,a_1,a_3\}$（$a_1,a_3$ から出る辺はすべて飽和しており、$a_2$ へは $s\to a_2$ が飽和していて、$b_1$ にも $b_2,b_3$ にも到達できない）。これが最小の $s$ 側集合 $S_{\min }$。このカットは $e_2(6),e_4(3),e_5(4),e_9(3),e_{10}(2)$ で容量 18。
残余グラフで $t$ に到達できる頂点は $\{t,b_2,b_3\}$（$b_2\to t$、$b_3\to t$ に残量 1 があり、$b_2,b_3$ に入る辺はすべて飽和、$b_1\to t$ は飽和で $b_1$ は $t$ に到達できない）。よって最大の $s$ 側集合は $S_{\max }=\{s,a_1,a_2,a_3,b_1\}$。このカットは $e_5(4),e_7(1),e_8(3),e_9(3),e_{10}(2),e_{11}(5)$ で容量 18。
任意の最小カット $S$ は $S_{\min }\subseteq S\subseteq S_{\max }$ を満たすので、すべての最小カットに含まれる辺は「始点が $S_{\min }$、終点が $S_{\max }$ の外」にある辺である。$e_5(a_1\to b_2)$、$e_9(a_3\to b_2)$、$e_{10}(a_3\to b_3)$ が該当し、ほかの辺は該当しない。

確認: $e_5$ を 5 にすると、$a_1\to b_2$ に 5 流せ（$s\to a_1$ は 8 まで可能）、$b_2$ への流入は 9 以下で $b_2\to t$ の容量 9 に収まり、総流量 19。$e_9$ や $e_{10}$ も同様に 19 になる。一方 $e_2$ を 7 にしても、カット $S_{\max }$ の容量 18 が変わらないので増えない。

よって答えは $\{5,9,10\}$。