最小全域木問題

最小木問題、あるいはカタカナ英語で最小スパニング木問題、最小スパニングツリー問題とも．

例

ある電力会社が全国に電気を送り届けるべく、日本中に電線を張り巡らせようと考えています．発電所と接続されていない家が無いようにもれなく電線を張り巡らせなければならないのですが、一方、材料費や工事のコストなどを考えると、なるべく無駄のない電線の張り方を選びたいという要求もあります．例えば、北海道と鹿児島を一本の長い電線で結ぶ、というのは凄く無駄に思えます．

このような問題を形式的に定義したものが最小全域木問題です．

定義（無向グラフの場合）

• 入力：グラフ 、コスト関数 ．
• 解：全域木．すなわち全ての頂点が接続されている木 ．
• 解のコスト：全域木に含まれる各辺のコストの和．
• 出力：コスト最小の解．

定義（有向グラフの場合）

• 入力：グラフ 、コスト関数 、根 ．
• 解： を根とした有向全域木．すなわち から全ての頂点への経路が存在する有向木 ．
• 解のコスト：有向全域木に含まれる各辺のコストの和．
• 出力：コスト最小の解．

なお、有向最小全域木問題を minimum arborescence problem（arborescence：亜喬木、あこうぼく）と言ったりもするらしいです．でも最小亜喬木問題とは言わないなぁ．

応用

電力網に限らず、道路でも電話でもガスでも水道でも、ネットワークを張り巡らせる形の問題は大体最小全域木問題に帰着できます．ただし、ネットワークの構築にもっと複雑な制約を与えたい場合も多々あるので、もっと複雑な問題に帰着することも多いです．

解法

無向最小全域木問題はプリム法やクラスカル法などよってグラフサイズの多項式時間で解くことができます．
有向最小全域木問題は Chu-Liu/Edmonds のアルゴリズムで同じく多項式時間で解くことができます．

一般化

グラフの全頂点を接続するのではなく、最低限接続すべき頂点を自由に選べるように拡張した問題を最小シュタイナー木問題といいます．最小全域木問題は多項式時間で解けることがわかっているのに対し、最小シュタイナー木問題は NP 困難です．詳細は最小シュタイナー木のページにて．