最小全域木
2008年11月9日 (日) 17:53時点におけるAlbeit-Kun (トーク | 投稿記録)による版
【さいしょうぜんいきぎ (minimum spanning tree)】
連結なグラフの辺に長さが定義されているとき, すべての頂点を含む木で辺の長さの和が最小のものを, そのグラフの最小全域木という. 特に頂点が平面(または一般の次元の空間)に固定され, 辺の長さが両端の頂点のユークリッド距離で与えられた完全グラフの最小全域木はユークリッド距離最小全域木と呼ばれる. これはドロネーグラフの部分グラフである.