組合せとグラフの理論(塩田)第8回 (4) 最小連結子問題

最小連結子問題の問題設定

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

クラスカル法

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

実行例

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

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

 これも「ステップ 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}$
  1. $S$ に $e_k$ を付加したグラフ $S_{tmp}$ には閉路 ${\scr C}$ が 1 つだけあります。( 第6回 Th.5 )
    $\qquad\qquad$
    $\textcolor{blue}{S_{tmp}}$$\textcolor{green}{{\scr C}}$
  2. $T$ は閉路を含まないので、$T$ に含まれない ${\scr C}$ の辺 $f$ が存在します。
  3. $S_{tmp}$ から $f$ を除去したグラフを $S'$ とおくと、これは再び $G$ の全域木になります。
    $\textcolor{blue}{S'}$
  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)$ が重み最小となります。(証明終)