木のグラフを操作する

• 木はグラフ
• 全域木は、すべてのノードが連結な木グラフ
• ノード数Nに対してエッジ数はN-1
• すべてのノードは少なくても１個の隣接ノードを持つ
• 辺の取り方を考える
• 木グラフをだんだんに大きくしていく
  • 初めはノードなし
  • ノード数１個の木グラフを作る
    • N個のノードから１個を選ぶ選び方はN通り
  • 次に、残ったN-1個のノードから１個を選び、すでにできている木のノードのうちの１個につなぐ(今は、ノード数１の木グラフだから、１個しかノードが選べない)
  • 以下、繰り返す。i番目のノードを連結するときには、(N-i+1)個のノードから１個を取り出す。その時点ですでにできている木には(i-1)個のノードがあるから、そのどれかに連結するとして、その選び方は(i-1)
  • このようにして作り上げていく場合の数は
  • Rで隣接行列を作るときには、上三角部分について、各行１個ずつ１を立てて、行列を作った上で(この段階でに相当する処理がなされている)、ノードN個の並び方を変える(この段階で通りが作られる)ことでできる

library(igraph)

N<-5
M<-matrix(0,N,N)
for(i in 1:(N-2)){
	M[i,sample((i+1):N,1)]<-1
}
M[N-1,N]<-1
M

s<-sample(1:N)

M<-M[s,s]
M

M2<-(M+t(M))
M2[lower.tri(M2)]<-0
M2
g<-graph.adjacency(M)
is.connected(g,"strong")
plot(g)