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

• 隣接行列Aのm乗の(i,j)要素の値は、i,j間のグラフ距離
• 3.1 Eigenvalues
• n完全グラフの隣接行列の固有値は、1がn-1重で-1が1個。p,q-完全2部グラフのそれはとp+q-2重の0
• Full-cycle permutation matrix of order nの場合、隣接行列の固有値は、
• 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
eigen(Q)[[1]]
exp(2*pi*1i*(0:(n-1))/n)

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

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
> 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
> 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
> 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)とすると、と言う関係がある
• 3.3 (上下)界
• 3.4 Energy of a graph
• 分子構造をグラフとしたとき、そのグラフの電子集合の持つエネルギーを考えることがある。Huckel theory。そこではで定義される。ただし、はグラフの固有値
• 3.5 Antiadjacency matrix of a directed graph