最小シュタイナー木

提供:ORWiki
移動: 案内, 検索

【さいしょうしゅたいなーき (minimum Steiner tree)】

平面(または一般の次元の空間)に配置された有限個の頂点をつなぐ長さ最小の木のこと. ただし, 最初に与えられた頂点以外にも頂点を設けてかまわない. 新しく設けた頂点をシュタイナー点という. 一般に, 同一の頂点集合に対して, シュタイナー木の方が最小全域木より短かい.

個人用ツール