2017-10-28

3 Adjacency Matrix ぱらぱらめくる『Graphs and Matrices』

隣接行列Aのm乗の(i,j)要素の値は、i,j間のグラフ距離
3.1 Eigenvalues
- n完全グラフの隣接行列の固有値は、1がn-1重で-1が1個。p,q-完全2部グラフのそれは $\sqrt{pq},-\sqrt{pq}$ とp+q-2重の0
- Full-cycle permutation matrix of order nの場合、隣接行列の固有値は、 $1,w,w^2,...,w^{n-1};w = e^{\frac{2\pi i}{n}$
- n頂点を結ぶパスグラフ(サイクルの両方向)のとき $2\cos{\frac{2\pi k}{n}}; k= 1,2,...,n$

my.full.cycle <- function(n){
	Q <- diag(n)
	Q <- Q[,c(n,1:(n-1))]
	Q
}
n <- 8
Q <- my.full.cycle(n)
C <- Q + t(Q)

P <- my.full.cycle(n)
P[n,1] <- 0
P <- P + t(P)

Q
plot(graph.adjacency(Q))
eigen(Q)[[1]]
exp(2*pi*1i*(0:(n-1))/n)

C
plot(graph.adjacency(C))
eigen(C)[[1]]
2*cos(2*pi*(0:(n-1))/n)

P
plot(graph.adjacency(P))
eigen(P)[[1]]
2*cos(2*pi*(1:n)/(n+1))

> n <- 8
> Q <- my.full.cycle(n)
> C <- Q + t(Q)
> 
> P <- my.full.cycle(n)
> P[n,1] <- 0
> P <- P + t(P)
> 
> Q
     [,1] [,2] [,3] [,4] [,5] [,6] [,7] [,8]
[1,]    0    1    0    0    0    0    0    0
[2,]    0    0    1    0    0    0    0    0
[3,]    0    0    0    1    0    0    0    0
[4,]    0    0    0    0    1    0    0    0
[5,]    0    0    0    0    0    1    0    0
[6,]    0    0    0    0    0    0    1    0
[7,]    0    0    0    0    0    0    0    1
[8,]    1    0    0    0    0    0    0    0
> plot(graph.adjacency(Q))
> eigen(Q)[[1]]
[1]  0.0000000+1.0000000i  0.0000000-1.0000000i -1.0000000+0.0000000i
[4] -0.7071068+0.7071068i -0.7071068-0.7071068i  1.0000000+0.0000000i
[7]  0.7071068+0.7071068i  0.7071068-0.7071068i
> exp(2*pi*1i*(0:(n-1))/n)
[1]  1.0000000+0.0000000i  0.7071068+0.7071068i  0.0000000+1.0000000i
[4] -0.7071068+0.7071068i -1.0000000+0.0000000i -0.7071068-0.7071068i
[7]  0.0000000-1.0000000i  0.7071068-0.7071068i
> 
> C
     [,1] [,2] [,3] [,4] [,5] [,6] [,7] [,8]
[1,]    0    1    0    0    0    0    0    1
[2,]    1    0    1    0    0    0    0    0
[3,]    0    1    0    1    0    0    0    0
[4,]    0    0    1    0    1    0    0    0
[5,]    0    0    0    1    0    1    0    0
[6,]    0    0    0    0    1    0    1    0
[7,]    0    0    0    0    0    1    0    1
[8,]    1    0    0    0    0    0    1    0
> plot(graph.adjacency(C))
> eigen(C)[[1]]
[1]  2.000000e+00  1.414214e+00  1.414214e+00  1.332268e-15  0.000000e+00
[6] -1.414214e+00 -1.414214e+00 -2.000000e+00
> 2*cos(2*pi*(0:(n-1))/n)
[1]  2.000000e+00  1.414214e+00  1.224606e-16 -1.414214e+00 -2.000000e+00
[6] -1.414214e+00 -3.673819e-16  1.414214e+00
> 
> P
     [,1] [,2] [,3] [,4] [,5] [,6] [,7] [,8]
[1,]    0    1    0    0    0    0    0    0
[2,]    1    0    1    0    0    0    0    0
[3,]    0    1    0    1    0    0    0    0
[4,]    0    0    1    0    1    0    0    0
[5,]    0    0    0    1    0    1    0    0
[6,]    0    0    0    0    1    0    1    0
[7,]    0    0    0    0    0    1    0    1
[8,]    0    0    0    0    0    0    1    0
> plot(graph.adjacency(P))
> eigen(P)[[1]]
[1]  1.8793852  1.5320889  1.0000000  0.3472964 -0.3472964 -1.0000000 -1.5320889
[8] -1.8793852
> exp(2*pi*1i*(1:n)/(n+1))
[1]  0.7660444+0.6427876i  0.1736482+0.9848078i -0.5000000+0.8660254i
[4] -0.9396926+0.3420201i -0.9396926-0.3420201i -0.5000000-0.8660254i
[7]  0.1736482-0.9848078i  0.7660444-0.6427876i
> eigen(P)[[1]]
[1]  1.8793852  1.5320889  1.0000000  0.3472964 -0.3472964 -1.0000000 -1.5320889
[8] -1.8793852
> 2*cos(2*pi*(1:n)/(n+1))
[1]  1.5320889  0.3472964 -1.0000000 -1.8793852 -1.8793852 -1.0000000  0.3472964
[8]  1.5320889

3.2 Determinant
- グラフのサブグラフであって、サイクルになるものと、単独のエッジになるものとをelementary subgraphと呼ぶ。サイクルであるelementary subgraphsの数をc(H),エッジ単独になるものの数をc1(H)とすると、 $det A =\sum (-1)^{n-c1(H)-c(H)}2^{c(H)}$ と言う関係がある
3.3 (上下)界
- 最大固有値の上界
3.4 Energy of a graph
- 分子構造をグラフとしたとき、そのグラフの電子集合の持つエネルギーを考えることがある。Huckel theory。そこでは $E_{\pi} = \sum |\lambda_i|$ で定義される。ただし、 $\lamba$ はグラフの固有値
3.5 Antiadjacency matrix of a directed graph
- AをAdajacency matrixとして、全成分が1の行列Jを使って $B= J-A$ としたこのBをantiadjacency matrixと言う
- Acyclic graphでハミルトニアンパスがあるときdet B= 1。そうでないときdet B= 0
- $det(xB+I) = \sum c_i x^i$ 、ただし、 $c_0=1$ で $c_i$ はi個のノードで出来た有向パスの数
3.6 Nonsingular trees
- 木のadjacency matrixはsingular のこともあり、nonsingularなこともあるが、nonsingularなのはperfect matchingをもつときに限り、perfect matcingを持てばnonsingular