計算機科学のブログ

木と探索 全域木と最小全域木 クラスカル法 重みを与える関数、辺、頂点、閉路、コスト

情報系のための離散数学 (猪股 俊光 (著)、南野 謙一 (著)、共立出版)の第8章(木と探索)、8.3(全域木と最小全域木)、8.3.3(クラスカル法)、問の8.12の解答を求めてみる。

第1段階。

e 1 = { b , d } e 2 = { a , c } , e 3 = { e , g } e 4 = { b , c } , e 5 = { c , d } , e 6 = { d , f } , e 7 = { e , f } e 8 = { a , b } , e 9 = { c , f } , e 10 = { d , e } e 11 = { b , 0 } E M = ϕ i = 1

第2段階。

E M = { e 1 }

第3段階。

i = 2

第2段階。

E M = { e 1 , e 2 }

第3段階。

i = 3

第2段階。

E M = { e 1 , e 2 , e 3 }

第3段階。

i = 4

第2段階。

E M = { e 1 , e 2 , e 3 , e 4 }

第3段階。

i = 5

第2段階。

閉路が生じるので含めない。

E M = { e 1 , e 2 , e 3 , e 4 }

第3段階。

i = 6

第2段階。

E M = { e 1 , e 2 , e 3 , e 4 , e 6 }

第3段階。

i = 7

第2段階。

E M = { e 1 , e 2 , e 3 , e 4 , e 6 , e 7 }

第3段階。

終了。

E M = { { b , d } , { a , c } , { e , g } , { b , c } , { d , f } , { e , f } }

最小全域木と最小コスト。

T M S T = ( V , E M ) ∑ e ∈ E M d ( e ) = 1 + 2 · 2 + 3 · 3 = 14