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=1c_iはi個のノードで出来た有向パスの数
  • 3.6 Nonsingular trees
    • 木のadjacency matrixはsingular のこともあり、nonsingularなこともあるが、nonsingularなのはperfect matchingをもつときに限り、perfect matcingを持てばnonsingular