最小全域木 の変更点

• 追加された行はこの色です。
• 削除された行はこの色です。
• 最小全域木 へ行く。

* 最小全域木 (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