グラフ理論の問題

$G=(V,E)$ を有限な連結な単純無向グラフとし、各辺 $e\in E$ に実数の重み $w(e)$ が与えられているとする。全域木の重みをその辺の重みの和で定め、重みが最小の全域木を最小全域木という。

$G$ の道 $P$ に対し、$P$ に含まれる辺の重みの最大値を $\beta (P)$ と書く。$T$ を $G$ の最小全域木とし、$u,v$ を $G$ の相異なる 2 頂点とする。$T$ の中で $u$ と $v$ を結ぶ（ただ 1 つの）道を $P_T$ とする。このとき、$G$ において $u$ と $v$ を結ぶ任意の道 $Q$ に対して
$$\beta (P_T)\le \beta (Q)$$
が成り立つことを証明せよ。

なお、木の基本的な性質（頂点数 $n$ の木の辺数は $n-1$ であること、木の 2 頂点を結ぶ道はただ 1 つであること、頂点数 $n$ で辺数 $n-1$ の連結グラフは木であること）は用いてよい。

頂点集合 $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$（最小カット）は全部でいくつあるか。

$G$ を頂点数 $n$、辺数 $e$ の連結な単純グラフとし、$G$ は平面に辺が交差しないように描かれている（平面グラフ）とする。この描画で平面が分けられてできる領域（外側の非有界な領域も含む）を面といい、その個数を $f$ とする。各面について、その境界をたどる閉路状の歩道の長さ（境界上の辺のうち、両側がともにその面であるものは 2 回数える）をその面の長さという。

$G$ のすべての頂点の次数が $3$ 以上であるとき、$G$ には長さが $5$ 以下の面が少なくとも 1 つ存在することを証明せよ。

なお、連結な平面グラフに対するオイラーの公式 $n-e+f=2$ と、すべての面の長さの和が $2e$ に等しいことは用いてよい。

頂点集合 $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=\{1,2,3,\dots ,30\}$ とする完全グラフ $K_{30}$ を考える。相異なる 2 頂点 $i,j$ を結ぶ辺 $\{i,j\}$ には、重み
$$w(i,j)=\frac{\mathrm{lcm}(i,j)}{\gcd (i,j)}$$
が与えられているとする（$\mathrm{lcm}$ は最小公倍数、$\gcd$ は最大公約数）。たとえば $w(4,6)=\frac{12}{2}=6$、$w(3,12)=\frac{12}{3}=4$ である。

この重みつきグラフの最小全域木の重み（最小全域木に含まれる辺の重みの総和）を求めよ。