グラフ理論の問題

頂点集合 $V=\{s,p,q,t\}$ をもつ有向ネットワークがあり、有向辺とその容量は次の $6$ 本である。$$s\to p:5,s\to q:4,p\to q:2,q\to p:3,p\to t:6,q\to t:3$$ 始点を $s$、終点を $t$ とする。$s$ を含み $t$ を含まない頂点集合 $S=\{s,q\}$ で定まる $s$-$t$ カットの容量 $$c(S)=\sum _{u\in S,v\notin S}c(u,v)$$ を求めよ。ただし、和は $u\in S$, $v\notin S$ である有向辺 $u\to v$ すべてについてとる。

頂点集合 $V=\{s,p,q,t\}$ をもつ有向ネットワークがあり、有向辺とその容量は次の $6$ 本である。
$$s\to p:5,s\to q:4,p\to q:2,q\to p:3,p\to t:3,q\to t:6$$
$s$ を始点、$t$ を終点とする。頂点の集合 $S=\{s,q\}$ で定まる $s$-$t$ カットの容量
$$c(S)=\sum _{u\in S,v\notin S}c(u,v)$$
を求めよ。ただし、和は $u\in S$, $v\notin S$ を満たす有向辺 $u\to v$ すべてについてとる。

頂点集合 $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,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$ の個数を、この順に組で答えよ。