「最小木問題」の版間の差分
ナビゲーションに移動
検索に移動
(新しいページ: '【さいしょうきもんだい (minimum spanning tree problem)】 各枝に重みの与えられた(無向)グラフにおいて, そのグラフ上に存在する全張木...') |
細 ("最小木問題" を保護しました。 [edit=sysop:move=sysop]) |
(相違点なし)
| |
2007年7月20日 (金) 10:20時点における版
【さいしょうきもんだい (minimum spanning tree problem)】
各枝に重みの与えられた(無向)グラフにおいて, そのグラフ上に存在する全張木(全域木)の中で枝の重みの総和が最小になるものを見出す組合せ最適化問題. それ自身も多くの応用例をもつが, より複雑な問題の子問題として利用されることも多い. クラスカル法やプリム法といった貪欲アルゴリズムにより多項式時間で解くことが可能である.