組合せとグラフの理論(塩田)第8回 (4) 最小連結子問題
最小連結子問題の問題設定
最小連結子問題 連結な重み付きグラフ $G$ において、重み最小の全域木 $T$ を求めよ。
※ コンピュータ間のケーブルの敷設コストが重みであれば、
最小コストでとりあえず通信ができる状態にしよう、ということです。
クラスカル法
この問題も決定版のアルゴリズムがあります。
Algorithm 14(クラスカル法)
- 入力:連結な重み付きグラフ $G$
- 出力:重み最小の全域木 $T$
- ( 辺集合として ) $T$ の初期値は空集合 $\emptyset$ とする。
- $n=$ ( $G$ の頂点数 ), $\,j = 1$ とおく。
- $T$ に付加しても閉路を作らない辺のうち、重み最小のものを $e_j$ とする。
- $T$ に $e_j$ を付加し、$j \leftarrow j + 1$.
- $j=n$ ならば $T$ を出力して終了。そうでなければ 3°に戻る。
クラスカル法の証明
$T$ の重み $w(T)$ の最小性を示しましょう。
- $S$ を $G$ の任意の全域木
- $e_k$ を、$S$ に含まれない $T$ の辺のうち番号最小のもの
とします。
Ex.15 の場合、$S$ を次の全域木とすると $e_k=e_2$ になります。
| $\qquad\qquad$ | |
$\require{color}\textcolor{red}{T}$ | | $\textcolor{blue}{S}$ |
- $S$ に $e_k$ を付加したグラフ $S_{tmp}$ には閉路 ${\scr C}$ が 1 つだけあります。( 第6回 Th.5 )
| $\qquad\qquad$ | |
$\textcolor{blue}{S_{tmp}}$ | | $\textcolor{green}{{\scr C}}$ |
- $T$ は閉路を含まないので、$T$ に含まれない ${\scr C}$ の辺 $f$ が存在します。
- $S_{tmp}$ から $f$ を除去したグラフを $S'$ とおくと、これは再び $G$ の全域木になります。
|
$\textcolor{blue}{S'}$ |
- $S'$ は $e_1$, $e_2$, $\cdots$, $e_k$ を含むことに注意してください。
- Alg.12 3°より $w(e_k) \leqq w(f)$ ですから、
$w(S') = w(S) + w(e_k) - w(f) \leqq w(S)$
- $S$ から $S'$ を作った操作を繰り返すと全ての $e_j$ を含む $T$ ができるので、
$w(T) \leqq \cdots \leqq w(S') \leqq w(S)$
従って $w(T)$ が重み最小となります。(証明終)