最小木問題

【さいしょうきもんだい (minimum spanning tree problem)】

各枝に重みの与えられた(無向)グラフにおいて, そのグラフ上に存在する全張木(全域木)の中で枝の重みの総和が最小になるものを見出す組合せ最適化問題. それ自身も多くの応用例をもつが, より複雑な問題の子問題として利用されることも多い. クラスカル法やプリム法といった貪欲アルゴリズムにより多項式時間で解くことが可能である.