- 追加された行はこの色です。
- 削除された行はこの色です。
- 最小全域木 へ行く。
* 最小全域木 (minimum spanning tree) [#a5f90e85]
//ここには %項目の説明を書いてください.よろしければ署名しておいてください.
無向グラフの全てのノードを結ぶ[[木]]を''全域木(spanning tree)''という.
辺に重みのある場合に,全域木の中で辺の重みの総和を最小にするものが''最小全域木 (minimum spanning tree)''.
-辺の重みとしてノード間のユークリッド距離を想定した場合,最小全域木は相対近傍グラフの部分グラフになる(文献1).
-グラフのノード数を n,辺数を m とするとき,O(m),O(n log n), O(m log log n)などのアルゴリズムが存在.
> -- しましま
** 関連項目 [#xce0e978]
//英語や同義語のあとに,#brで区切って関連する項目をリストしてください.
-[[minimum spanning tree]]
-[[MST]]
#br
-[[全域木]]
-[[spanning tree]]
#br
-[[グラフ]]
-[[計算幾何]]
-[[相対近傍グラフ]]
-[[最近傍グラフ]]
#br
-[[検索:最小全域木]]
** リンク集 [#t6b42e7e]
//関連するWWW資源があればリンクしてください.
-[[Wikipedia:Minimum_spanning_tree]]
-[[Wikipedia:Prim's_algorithm]]
-[[Wikipedia:Kruskal's_algorithm]]
-[[MathWorld:MinimumSpanningTree]]
-[[PlanetMath:MinimumSpanningTree]]
-[[Wikipedia.jp:スパニング木]]
** 関連文献 [#o1ccb4a8]
//この%項目%に関連する書籍や論文を紹介してください.
-文献1:G.T.Toussaint "The relative neighborhood graph of a finite planar set" Pattern Recognition, vol.12, no.4 (1980)~
[[GoogleScholarAll:The relative neighborhood graph of a finite planar set]]
-[[Book/Algorithms for Clustering Data]] 3.3.6