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

離散数学
10. 最小全域木
五島
DATE
:
離散数学
最小全域木
 グラフの全域木 (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
}
証明
 2 の方を選んで MST が得られると仮定
1
0
U
V
2
V : visited
U : unvisited
F : frontier
離散数学
証明
 すると，こうなるが…
1
0
U
V
2
V : visited
U : unvisited
F : frontier
離散数学
証明
 こっちの方が 1 だけ小さい
 V，U はそれぞれ連結であることに注意
1
0
U
V
2
V : visited
U : unvisited
F : frontier
離散数学

Download Report