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

トップ   編集 差分 バックアップ 添付 複製 名前変更 リロード   新規 一覧 単語検索 最終更新   ヘルプ   最終更新のRSS