最小全域木とは？
さいしょうぜんいきぎ
最小全域木とは、重み付きグラフにおいて、すべての頂点を連結しながら辺の重みの合計が最も小さくなる木（閉路なしの部分グラフ）のことです。
最小全域木（Minimum Spanning Tree、MST）は、重み付き連結グラフにおいて、全頂点を含む部分グラフ（全域木）の中で、辺の重みの総和が最小となるものを指します。全域木は閉路を持たずにすべての頂点を連結する木構造です。
最小全域木は、次のような場面で自然に登場します。
最小全域木を求める代表的なアルゴリズムには以下があります。プリム法は頂点を1つずつ選びながら木を育てる手法、クラスカル法は辺を重みが小さい順に選んで閉路ができなければ追加していく手法です。いずれも貪欲法（グリーディアルゴリズム）に基づいており、効率よく正解を導けます。
グラフの辺の重みが異なる場合、最小全域木は一意に定まることが保証されています（同一重みの辺がある場合は複数存在する可能性があります）。コンピューターサイエンスの教育においても定番のアルゴリズム問題として取り上げられます。
使い方・例文
10個の都市を通信ケーブルで結ぶとき、各都市間のケーブル敷設コストが異なる場合、最小全域木を使うことで全都市をつなぐための最小総費用と配線経路を求めることができます。
この用語をシェア
最終更新: