木と探索 全域木と最小全域木 最小全域木 辺、重み付きグラフ(ラベル付きグラフ)、コスト
情報系のための離散数学 (猪股 俊光 (著)、南野 謙一 (著)、共立出版)の第8章(木と探索)、8.3(全域木と最小全域木)、8.3.2(最小全域木)、問の8.11の解答を求めてみる。
g, e, b, a, c, f, d
コストは4 + 3 + 3 + 4 + 2 + 2 = 18
4 + 3 + 2 + 2 + 3 + 5 = 19
4 + 1 + 3 + 5 + 4 + 2 = 19
4 + 3 + 1 + 3 + 4 + 2 = 17
4+3+3+3+1+3=18