組合せとグラフの理論（塩田）第8回 (4)　最小連結子問題
前へ / 戻る / 次へ

問題設定

最小連結子問題　連結な重み付きグラフ $G$ において、重み最小の全域木 $T$ を求めよ。
※　コンピュータ間のケーブルの敷設コストが重みであれば、 最小コストでとりあえず通信ができる状態にしよう、ということです。

クラスカル法

　この問題も決定版のアルゴリズムがあります。
Algorithm 14（クラスカル法）
  • 入力：連結な重み付きグラフ $G$
  • 出力：重み最小の全域木 $T$
  1. ( 辺集合として ) $T$ の初期値は $\emptyset$ とする。
  2. $n=$ ( $G$ の頂点数 ), $\,j = 1$ とおく。
  3. $T$ に付加しても閉路を作らない辺のうち、重み最小のものを $e_j$ とする。
  4. $T$ に $e_j$ を付加する。
  5. $j \leftarrow j + 1$.
  6. $j=n$ ならば $T$ を出力して終了。そうでなければ 3°に戻る。

実行例

Ex.15　次のグラフでクラスカル法を実行してみましょう。
　重みの小さい順に辺をソートして考えます。
  1. 重み $2$： $AB=e_1$
  2. 重み $3$： $BD=e_2$
  3. 重み $4$： $AD$ ... 閉路を作るので不可
  4. 重み $5$： $ED=e_3$
  5. 重み $6$： $AE$ ... 閉路を作るので不可
  6. 重み $6$： $BE$ ... 閉路を作るので不可
  7. 重み $7$： $BC=e_4$
(1) →　 (2) →
(3) →　 (4) →
(5) →　 (6) →
(7) で終了。

※　絵はひとつあれば十分作業できます。

クラスカル法の証明

$T$ の重み $w(T)$ の最小性を示しましょう。
  • $S$ を $G$ の任意の全域木
  • $e_k$ を、$S$ に含まれない $T$ の辺のうち番号最小のもの
とします。
  1. $S$ に $e_k$ を付加したグラフ $S_{tmp}$ には閉路 $C$ が 1 つだけあります。( 第6回 Th.5 )
  2. $T$ は閉路を含まないので、$T$ に含まれない $C$ の辺 $f$ が存在します。
  3. $S_{tmp}$ から $f$ を除去したグラフを $S'$ とおくと、これは再び $G$ の全域木になります。
  4. $S'$ は $e_1$, $e_2$, $\cdots$, $e_k$ を含むことに注意してください。
  5. Alg.12 3°より $w(e_k) \leqq w(f)$ ですから、
    $w(S') = w(S) + w(e_k) - w(f) \leqq w(S)$
  6. $S$ から $S'$ を作った操作を繰り返すと全ての $e_j$ を含む $T$ ができるので、
    $w(T) \leqq \cdots \leqq w(S') \leqq w(S)$
従って $w(T)$ が重み最小となります。(証明終)

前へ / 戻る / 次へ