２章 駆け足で読む『トポロジカル・インデックス』その２

• 毛虫グラフを描く

library(igraph)

n <- 8

ke <- sample(1:5,n,replace=TRUE)

e.l <- NULL

for(i in 2:n){
	e.l <- rbind(e.l, c(i-1,i))
}
v.id <- n+1
for(i in 1:n){
	for(j in 1:ke[i]){
		e.l <- rbind(e.l, c(i,v.id))
		v.id <- v.id +1
	}
}

g <- graph.edgelist(e.l)
plot(g)

• トポロジカル・インデックスの定義
  • グラフGに互いに隣り合わないk個の辺を選ぶ組み合わせの数を、第k非隣接数と呼び、と表す
  • 
• 経路グラフのトポロジカル・インデックスはフィボナッチ数だと言う
  • 経路グラフの第k非隣接数はパスカルの三角形を斜めに読んだものだと言う
  • まずはパスカルの三角形

pascal.triangle <- function(n){
	ret <- list()
	ret[[1]] <- 1
	if(i > 1){
		ret[[2]] <- c(1,1)
		if(i > 3){
			for(i in 3:n){
				ret[[i]] <- c(1,ret[[i-1]][-(i-1)] + ret[[i-1]][-1],1)
			}
		}
		
	}
	
	ret
}
pascal.triangle(10)

• • 斜めにするために、パスカルの三角形を一度作った上で、「ナナメに」登録する

top.idx.path.graph <- function(n){
	pscl <- pascal.triangle(n+1)
	ret <- list()
	for(i in 0:n){
		if(i == 0){
			ret[[i+1]] <- rep(0,1)
		}else{
			ret[[i+1]] <- rep(0,i-1)
		}
	}
	for(i in 1:length(pscl)){
		for(j in 1:length(pscl[[i]])){
			if(i+j-1 <= n+1){
				ret[[i+j-1]][j] <- pscl[[i]][j]
			}
			
		}
	}
	ret
}
top.idx.path.graph(7)

• • これが、第k非隣接数

> top.idx.path.graph(7)
[[1]]
[1] 1

[[2]]
[1] 1

[[3]]
[1] 1 1

[[4]]
[1] 1 2

[[5]]
[1] 1 3 1

[[6]]
[1] 1 4 3 0

[[7]]
[1] 1 5 6 1 0

[[8]]
[1]  1  6 10  4  0  0

• • フィボナッチ数列はこの和

tp <- top.idx.path.graph(7)
lapply(tp,sum)

> tp <- top.idx.path.graph(7)
> lapply(tp,sum)
[[1]]
[1] 1

[[2]]
[1] 1

[[3]]
[1] 2

[[4]]
[1] 3

[[5]]
[1] 5

[[6]]
[1] 8

[[7]]
[1] 13

[[8]]
[1] 21

• 行列・固有値・特性多項式・非隣接数・トポロジカルインデックスの関係
  • 行列の特徴を抽出したものに固有値(のセット)がある
  • 固有値のセットを用いた式を多項式に書き下したものが特性多項式
  • 特性多項式の係数(の絶対値)がグラフの隣接行列の場合には非隣接数
  • 非隣接数の総和がトポロジカルインデックス
  • 行列式の計算は比較的簡単
• 行列・固有値・特性多項式・非隣接数・トポロジカルインデックスの情報量
  • 行列は「フル」
  • 固有値のセット、特性多項式、非隣接数のセットは同等
  • 行列式とトポロジカルインデックスは同等。ただし計算しやすさは行列式の方が上(行列のパーマネントの計算が大変なのと似たようなこと)