最大流最小カット定理

頂点集合 $V=\{s,u,v,t\}$ をもつ有向ネットワークがあり、有向辺とその容量は次の $5$ 本である。
$$s\to u:3,s\to v:2,u\to v:1,u\to t:2,v\to t:4$$
$s$ を入口、$t$ を出口とする。$s\in S,t\notin S$ を満たす頂点の部分集合 $S\subset V$ を $s$-$t$ カットといい、その容量を $c(S)={\sum }_{x\in S,y\notin S}c(x,y)$（$x$ から $y$ への辺がないときは $c(x,y)=0$）と定める。

$s$ から $t$ への最大流の値と、容量が最小となる $s$-$t$ カット $S$ の個数を、この順に組で求めよ。

頂点集合 $V=\{s,a,b,t\}$ をもつ有向ネットワークがあり、有向辺とその容量は次の $5$ 本である。$$s\to a:3,s\to b:2,a\to b:1,a\to t:2,b\to t:3$$ $s$ を始点、$t$ を終点とする。ここで $s$-$t$ カットとは、$s\in S$ かつ $t\notin S$ を満たす $V$ の部分集合 $S$ のことで、その容量を $c(S)={\sum }_{u\in S,v\notin S}c(u,v)$ と定める。$s$ から $t$ への最大流の値と、容量が最小となる $s$-$t$ カット $S$ の個数を、この順に組で答えよ。

頂点集合 $V=\{s,u,v,t\}$ をもつ有向ネットワークがあり、有向辺とその容量は次の $5$ 本である。$$s\to u:6,s\to v:2,u\to v:1,u\to t:4,v\to t:5$$ ソースを $s$、シンクを $t$ とするとき、$s$ から $t$ への最大流の値を求めよ。

頂点集合 $V=\{s,a,b,c,t\}$ をもつ有向ネットワークがあり、有向辺とその容量は次の 7 本である。
$$s\to a:4,s\to b:3,a\to b:2,a\to c:2,b\to c:1,b\to t:3,c\to t:3$$
ここで、$s\in S$ かつ $t\notin S$ をみたす頂点の部分集合 $S\subseteq V$ を $s$-$t$ カットとよび、その容量を、始点が $S$ に属し終点が $V\setminus S$ に属する有向辺の容量の和と定める（$V\setminus S$ から $S$ へ向かう辺は数えない）。

容量が最小となる $s$-$t$ カット $S$ は何個あるか。

$x$ を正の実数とする。頂点集合 $V=\{s,a,b,c,d,t\}$ をもつ有向ネットワークがあり、有向辺とその容量は次の 8 本である。
$$\begin{array}{llll}s\to a:7,& s\to b:6,& a\to c:4,& a\to d:x,\\ b\to c:2,& b\to d:5,& c\to t:6,& d\to t:8\end{array}$$
始点を $s$、終点を $t$ とする $s$-$t$ フローの最大値を $F(x)$ とする。$x$ が正の実数全体を動くとき、$F(x)$ が最大となるような $x$ の最小値を求めよ。

頂点集合 $V=\{s,a,b,c,d,t\}$ をもつ有向ネットワークがあり、有向辺とその容量は次のとおりである。
$$\begin{array}{lll}s\to a:10,& s\to b:8,& a\to b:3,\\ a\to c:4,& a\to d:5,& b\to c:1,\\ b\to d:7,& d\to c:3,& c\to t:10,\\ d\to t:7& & \end{array}$$
始点を $s$、終点を $t$ とするとき、$s$ から $t$ への流れの値の最大値を求めよ。

$V$ を有限集合、$E\subseteq \{(u,v)\in V\times V\mid u\ne v\}$ を有向辺の集合とし、各辺 $e\in E$ に容量 $c(e)\ge 0$（実数）が与えられたネットワーク $N=(V,E,c)$ を考える。相異なる 2 頂点 $s$（始点）と $t$（終点）を固定する。

$s\in S$, $t\notin S$ を満たす部分集合 $S\subseteq V$ を $s$-$t$ カットといい、その容量を
$$c(S)=\sum _{(u,v)\in E,u\in S,v\notin S}c(u,v)$$
と定める。容量が最小の $s$-$t$ カットを最小カットという。

$S_1$, $S_2$ がともに最小カットであるとき、$S_1\cap S_2$ も最小カットであることを証明せよ。

なお、フロー（各辺で $0\le f(e)\le c(e)$ を満たし、$s,t$ 以外の各頂点で流入量と流出量が等しい関数 $f:E\to \mathbb{R}$）の値 $|f|$ について、次の 2 つは用いてよい。
- 任意の $s$-$t$ カット $S$ に対して $|f|=\sum _{(u,v)\in E,u\in S,v\notin S}f(u,v)-\sum _{(u,v)\in E,u\notin S,v\in S}f(u,v)$
- 最大流最小カット定理（最大フローの値は最小カットの容量に等しい）

頂点集合 $V=\{s,a,b,c,d,e,t\}$ をもつ有向ネットワークがあり、有向辺とその容量は次の $11$ 本である。
$$\begin{array}{llll}s\to a:3,& s\to b:2,& a\to b:1,& a\to c:2,\\ b\to c:1,& b\to d:2,& c\to d:1,& c\to e:1,\\ c\to t:3,& d\to e:2,& e\to t:2.& \end{array}$$
ここで $s$-$t$ カットとは、$s\in S$、$t\notin S$ を満たす部分集合 $S\subset V$ のことをいい、その容量を $S$ から $V\setminus S$ へ向かう有向辺の容量の総和で定める。容量が最小となる $s$-$t$ カット $S$（最小カット）は全部でいくつあるか。

頂点集合
$$V=\{s,t,a_1,a_2,a_3,a_4,a_5,b_1,b_2,b_3,b_4,b_5\}$$
をもつ有向ネットワーク $N$ を考える。$N$ の有向辺とその容量は次の $35$ 本である。
- $i=1,2,3,4,5$ に対し、辺 $s\to a_i$。容量は順に $5,5,5,1,1$
- すべての $i,j\in \{1,2,3,4,5\}$ に対し、辺 $a_i\to b_j$（$25$ 本）。容量はすべて $1$
- $j=1,2,3,4,5$ に対し、辺 $b_j\to t$。容量は順に $5,5,3,2,2$

$N$ における $s$ から $t$ への最大流の流量を求めよ。

頂点集合 $V=\{s,a_1,a_2,a_3,b_1,b_2,b_3,t\}$ をもつ有向ネットワークがあり、有向辺 $e_1,\dots ,e_{13}$ とその容量は次のとおりである。
$$\begin{array}{lll}{e}_1:s\to a_1,8& e_2:s\to a_2,6& e_3:s\to a_3,7\\ e_4:a_1\to b_1,3& e_5:a_1\to b_2,4& e_6:a_2\to b_1,4\\ e_7:a_2\to b_2,1& e_8:a_2\to b_3,3& e_9:a_3\to b_2,3\\ e_{10}:a_3\to b_3,2& e_{11}:b_1\to t,5& e_{12}:b_2\to t,9\\ e_{13}:b_3\to t,6& & \end{array}$$
$s$ を始点、$t$ を終点とする。ほかの辺の容量はそのままにして、ある 1 本の辺 $e_i$ の容量だけを $1$ 増やしたとき、$s$ から $t$ への最大流の値が元の値より大きくなるような番号 $i$ をすべて求め、集合で答えよ。