パッケージveganのspantree()関数は、距離行列を引数として、最小全域木を返す # 点はk次元空間 # 描図は2次元 library(vegan) Npt<-100 k<-4 X<-matrix(0,Npt,k) for(i in 2:Npt){ X[i,]<-X[i-1,]+rnorm(k) } MST<-spantree(dist(X)) plot(X[,1:2]) # MST[[…

参考こちら ２つの主なテーマ ユークリッド空間上のランダムな点(の完全グラフ)におけるユークリッド最小全域木の重みの分布 点を固定(グラフも固定、完全グラフとは限らない(多分))して(エッジの重みをランダムに振った上での最小全域木の重みの分布

最小全域木もいろいろある(距離の定め方によって) 特にユークリッド距離での最小全域木の場合には、選択される辺に幾何学的な制約をして候補を減らせるので、通常の解探索より速くできる(Euclidean menimum spanning treeのWiki記事) 完全グラフから最小全域…