最小全域木

【さいしょうぜんいきぎ (minimum spanning tree)】

連結なグラフの辺に長さが定義されているとき, すべての頂点を含む木で辺の長さの和が最小のものを, そのグラフの最小全域木という. 特に頂点が平面(または一般の次元の空間)に固定され, 辺の長さが両端の頂点のユークリッド距離で与えられた完全グラフの最小全域木はユークリッド距離最小全域木と呼ばれる. これはドロネーグラフの部分グラフである.