グラフ理論の問題

最大流最小カット定理により、$F(x)$ は $s$-$t$ カットの容量の最小値に等しい。$s$ を含み $t$ を含まない頂点集合 $S$ に対し、$S$ から $V\setminus S$ へ向かう辺の容量の和をカット容量とする。

主なカットの容量を計算すると次のようになる。
- $S=\{s\}$: $7+6=13$
- $S=\{s,a\}$: $s\to b,a\to c,a\to d$ より $6+4+x=10+x$
- $S=\{s,b\}$: $7+2+5=14$
- $S=\{s,a,b\}$: $4+x+2+5=11+x$
- $S=\{s,a,b,c\}$: $x+5+6=11+x$
- $S=\{s,a,b,d\}$: $4+2+8=14$
- $S=\{s,a,b,c,d\}$: $6+8=14$
- $S=\{s,a,c\}$: $6+x+6=12+x$

ほかのカット（$\{s,c\}$, $\{s,d\}$, $\{s,a,d\}$, $\{s,b,c\}$, $\{s,b,d\}$, $\{s,c,d\}$, $\{s,a,c,d\}$, $\{s,b,c,d\}$）の容量はそれぞれ $19,21,18,18,17,27,20,21$ で、いずれも $13$ 以上である。

したがって
$$F(x)=\min \{13,10+x\}$$
である。$F(x)\le 13$ であり、$F(x)=13$ となるのは $10+x\ge 13$、すなわち $x\ge 3$ のときである。

実際、$x=3$ のとき次のフローが容量制約と流量保存則を満たし、値は $13$ となる。
$$s\to a:7,s\to b:6,a\to c:4,a\to d:3,b\to c:1,b\to d:5,c\to t:5,d\to t:8$$
（$a$: 入 $7$・出 $4+3$、$b$: 入 $6$・出 $1+5$、$c$: 入 $4+1$・出 $5$、$d$: 入 $3+5$・出 $8$。）

一方 $x<3$ ではカット $S=\{s,a\}$ の容量が $10+x<13$ なので $F(x)<13$ である。よって求める最小値は $3$ である。

$s$ から出る辺の容量の和は $7+6=13$ なので $F(x)\le 13$ であり、これは $x$ によらない上限である(カット $\{s\}$)。したがって $F(x)=13$ となる条件を調べる。
$F=13$ には $s\to a$、$s\to b$ が両方飽和することが必要。頂点 $a$ から出る流量は $7$ で、$a\to c\le 4$、$a\to d\le x$ だから $4+x\ge 7$、すなわち $x\ge 3$ が必要。
逆に $x\ge 3$ のとき、$s\to a=7$, $s\to b=6$, $a\to c=4$, $a\to d=3$, $b\to c=2$, $b\to d=4$, $c\to t=6$, $d\to t=7$ はすべて容量以内($a\to d=3\le x$, $b\to d=4\le 5$, $c\to t=6\le 6$, $d\to t=7\le 8$)で、各中間頂点で流入=流出($a$: 7=4+3, $b$: 6=2+4, $c$: 6=6, $d$: 7=7)。流量は $13$ である。
$x<3$ のとき、カット $\{s,a,b,c,d\}$ と $\{t\}$ ではなく、$a$ に関する制約から $s\to a$ の流量は $\le 4+x<7$ なので $F\le (4+x)+6<13$。よって $F(x)$ の最大値は $13$ で、最大となる $x$ は $x\ge 3$、最小値は $3$。