計算機科学のブログ

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

本の表紙

情報系のための離散数学
 楽天ブックス
Yahoo!ショッピング
au PAY マーケット

学習環境

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

\begin{array}{l} E_{M} = ϕ \\ E_{M} = {{c, f}} \\ E_{M} = {{c, f}, {b, c}} \\ E_{M} = {{c, f}, {b, c}, {c, d}} \\ E_{M} = {{c, f}, {b, c}, {c, d}, {d, e}} \\ E_{M} = {{c, f}, {b, c}, {c, d}, {d, e}, {a, b}} \\ E_{M} = {{c, f}, {b, c}, {c, d}, {d, e}, {a, b}, {a, h}} \\ E_{M} = {{c, f}, {b, c}, {c, d}, {d, e}, {a, b}, {a, h}, {c, g}} \end{array}

よって、最小全域木は

T_{M S T} = (V, E_{M})

最小コストは

\begin{array}{l} \sum_{e \in E_{M}} d (e) \\ = 1 + 2 + 2 + 2 + 3 + 3 + 4 \\ = 17 \end{array}