最小木 - 坂井・入江研究室 [東京大学情報

離散数学
10. 最小全域木
五島
離散数学
最小全域木
 グラフの全域木 (spanning tree,極大木,張る木)
 そのグラフの全頂点を含む木
 グラフ探索アルゴリズムで自然に求まる
 辺重みつきグラフの最小全域木 (minimum spanning tree; MST)
 全域木の中で辺の重みの和が最小のもの
 辺に重みがない(重み一様)場合: 再び単なるグラフ探索
 辺に重みがある場合:少しややこしい

幅優先探索 vs Dijkstra の違いと似た事情
離散数学
例
2
5
1
4
3
1
3
2
3
2
3
5
4
7
1
3
2
コスト(重み)=17 (どうやら最小)
コスト(重み)=27
2
2
5
5
3
1
1
4
3
2
2
3
1
3
3
5
4
3
4
2
2
1
3
3
3
5
7
7
1
2
3
1
2
4
離散数学
応用
 ネットワーク敷設
 頂点: 拠点.
 辺 (a, b) : 拠点 a, b 間にケーブルの敷設が可能で,重みがその費用
 全域木:全拠点をつなぐのに最低限必要辺の集合(これ以上一本も辺を取り
除けない)
 MST: 総費用最小のケーブル敷設計画
離散数学
アルゴリズム
 Prim
 再び幅優先探索(または Dijkstra 法)と類似
 指定した一頂点から,「最小木に属するはずの辺」を順次加えていく
 Kruskal
 省略(石畑の教科書など参照)
離散数学
Prim のアルゴリズム
 再び!優先度つきグラフ探索の一種
 頂点 u の優先度: 訪問済み頂点
 u なる辺の重みの最小値
 つまり「訪問済み」  「未訪問」を
橋渡す辺の中で最小の辺(の終
点)を加えていく
 右図の辺の中の最小値
訪問済み
離散数学
Primのアルゴリズム: 擬似コード
prim (G)
{
V = {};
2
5
3
1
4
1
3
2
3
2
3
3
5
while (V  A) {
pick u  F that minimizes weight;
V = V + { u };
}
}
4
7
1
2
}
離散数学
証明
F
2
0
V : visited
U : unvisited
F : frontier
V
1
2
U