グラフのラプラシアン

• こちらで２次元・３次元、その他の拡散を扱っている。それと関係する話し

数学セミナー 2011年 05月号 [雑誌]

• 数学セミナー５月号の記事『線形代数と数え上げ(全域木の数え上げ)』という記事がある
• グラフのラプラシアンが扱われる
• グラフのラプラシアンについての関連記事
  • 特殊な形の行列式
  • 特殊な形の行列式(その２)
  • 特殊な形の行列式(その３)
• 
• 
  • これは、平面格子に関するラプラシアン
• グラフへの拡張は、平面格子にある点のラプラシアンが、その点への辺の出入りで決まっている
  • 
    • 慣習により、これの負を採ったものらしいが…
    • また、この成分和をグラフの隣接行列形式(ノード数NにつきNxNの行列)で表すらしいが…
• さて、証明は数セミに任せることとして、Rを使ってその様子を

連結な無向グラフGのラプラシアンLの余因子(Lからi行j列を除いた行列Lijの行列式に[tex:(-1)^{i+j}]をかけたものは、i,jの選び方によらず一定である。
そして、その値は、Gの全域木の重み(全域木の重みとは、全域木の辺の重みの総積)の総和に等しい。
今、辺の重みを１とすれば、全域木の重みは１であるから、その総和は、全域木の総数に等しい。
さらに、今、Lの余因子は、全頂点に関して、「辺のありなしによらない計算をしていると考えれば(重み0の辺を含む全域木も考慮する)」、「全域木として成立している(つながっている)木の重みは１」で、「全域木として成立していない(つながっていない)木の重みは０」であるから、Lの余因子が全域木の個数を数え上げられるのは、余因子が、辺の重みによらず(辺の存在の有無によらず)、その『木的な』つながりパターンを数え上げてくれること、そして、そのときに辺の重みを「０，１」〜「辺なし、辺あり」に対応付けることが、『全域木』の個数の数え上げである、ということに由来する。

#まず、適当に「連結グラフ」を作る
#頂点を増やすごとに、必ず、それまでにできている木の頂点に連結させることで作成している
N<-10 # 頂点数
# 連結行列作成
M<-matrix(0,N,N)
for(i in 2:N){
	tmp<-sample(1:(i-1),sample(1:(i-1),1))
	M[i,tmp]<-1
}
M

M2<-M+t(M)
M2 # 連結行列
# ラプラシアンの作成
d<-apply(M2,1,sum)
D<-diag(d)

L<-D-M2
L
# 余因子がi,jのとり方によらないことの確認

# igraphパッケージを使って、描図

library(igraph)
gtest<-graph.adjacency(M2,mode="undirected")
plot(gtest)