「最小全域木」の版間の差分
ナビゲーションに移動
検索に移動
(新しいページ: ''''【さいしょうぜんいきぎ (minimum spanning tree)】''' 連結なグラフの辺に長さが定義されているとき, すべての頂点を含む木で辺の長...') |
細 ("最小全域木" を保護しました。 [edit=sysop:move=sysop]) |
(相違点なし)
| |
2007年7月20日 (金) 10:21時点における版
【さいしょうぜんいきぎ (minimum spanning tree)】
連結なグラフの辺に長さが定義されているとき, すべての頂点を含む木で辺の長さの和が最小のものを, そのグラフの最小全域木という. 特に頂点が平面(または一般の次元の空間)に固定され, 辺の長さが両端の頂点のユークリッド距離で与えられた完全グラフの最小全域木はユークリッド距離最小全域木と呼ばれる. これはドロネーグラフの部分グラフである.