グラフ理論の問題

$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,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,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$ をすべて求め、集合で答えよ。

頂点集合 $V=\{a,b,c,d,e,f,g\}$ をもつ重みつき単純無向グラフ $G$ があり、辺とその重みは次の 11 本である。
$$\begin{array}{llll}ab:4,& ac:2,& bc:1,& bd:5,\\ cd:8,& ce:10,& de:2,& df:6,\\ ef:3,& eg:7,& fg:1& \end{array}$$
ここで、たとえば $ab:4$ は頂点 $a$ と $b$ を結ぶ重み $4$ の辺を表す。道の長さをその道に含まれる辺の重みの和で定めるとき、頂点 $a$ から頂点 $g$ への最短路の長さを求めよ。

頂点集合 $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$ への最大流の値を求めよ。