【さいしょうぜんいきぎ】
最小全域木 とは？
最終更新:
💡 「全員つなげて、コスト最小」を実現するグラフの最適解！
連結な重み付き無向グラフで、全頂点を閉路なしにつなぎ、辺のコストの合計が最小になる木。最小全域木は求める結果で、クラスカル法やプリム法はそれを求めるアルゴリズム。
📌 このページのポイント
- 全頂点を含み、閉路を持たない接続を選ぶ
- 各頂点への最短経路ではなく、選んだ辺のコストの合計を最小にする
- クラスカル法やプリム法で求められる
- 同じコストの辺があると、最小全域木が複数ある場合もある
ひよこ 何を最小にするの？
ペンギン先生 選んだ辺のコストの合計だよ。全頂点がつながる、辺にコストを付けた無向グラフで、全頂点をつなぎ、閉路を作らない木を考える。例えば配線の費用を辺のコストとして付ければ、合計費用が最小の接続を選ぶ問題になるね
ひよこ 最短経路とは違うの？
ペンギン先生 違うよ。ある出発点から各頂点までの距離を最小にする問題ではないんだ。最小全域木では、全体をつなぐために選んだ辺の合計を比べる。ある二点の間では遠回りになることもあるよ
ひよこ どうやって求めるの？
ペンギン先生 クラスカル法は辺をコストの小さい順に調べ、閉路を作らないものを選ぶ。プリム法は一つの頂点から始め、今の木と木の外を結ぶ辺のうち最も軽いものを加えて広げるよ。今いる頂点の隣だけを見ればよいわけではないんだ
ひよこ 安い順で必ず一つの答えになる？
ペンギン先生 これらの方法は最小の合計を求められるけれど、同じコストの辺があると、同じ最小値の木が複数ある場合もあるよ。グラフが連結でなければ全頂点を一つの木につなげず、各連結部分の木を合わせた最小全域森を考えるんだ
ひよこ 実際の配線も、この木だけで十分？
ペンギン先生 これはコストの合計を最小にするモデルだよ。木の辺が一つ切れると接続が分かれるので、障害に備えた予備の接続や容量などが必要なら、別の条件も考えよう。最小全域木だけで実際のネットワーク設計が完成するわけではないね
まとめ：ざっくりこれだけ覚えればOK！
「最小全域木」って出てきたら「全頂点を閉路なしにつなぐ、コストの合計が最小の木」と思えばだいたいOK！
📖 おまけ：英語の意味
「Minimum Spanning Tree（MST）」 ＝ 最小全域木
💬 Spanning（全域）はグラフの全頂点をカバーするという意味で、Tree（木）は閉路のない連結グラフのことだよ