ただのメモ

• グラフGの上にサブグラフsを置く。サブグラフ上の走査とグラフ全体の走査との効率に値を与えるための仕組みは？
• グラフにおけるトポロジカル・インデックスの計算が漸化式化することと、グラフで表現した複体・部分集合に定める演算とに共通項がある？
• 演算表

# 要素数kの集合のべき集合
# 各行がべき集合の要素
# 1が立っている列が「あり」
k <- 3
x <- as.matrix(expand.grid(rep(list(c(0,1)),k)))
# べき集合に「値」を与えて、IDとする
x.val <- apply(t(x) * 2^(0:(k-1)), 2, sum)

# 演算１
# ２つの要素の集合和
f1 <- function(x,y){
	k <- length(x)
	tmp <- as.matrix(expand.grid(rep(list(c(0,1)),k)))

	tmp.val <- apply(t(tmp) * 2^(0:(k-1)), 2, sum)

	z <- sign(x+y)
	z.val <- sum(z*2^(0:(length(x)-1)))
	which(z.val == tmp.val)
}

# べき集合の要素について総当たりをして、演算f1の結果がどの要素になったかを行列で表す
# 単位元の存在は、各行に自身と同じIDがあることで示される
# 逆元の存在は、各行に1があることで示される

m1 <- matrix(0,length(x[,1]),length(x[,1]))
for(i in 1:length(x[,1])){
	i.val <- which(sum(x[i,]*2^(0:(length(x[i,])-1))) == x.val)
	for(j in 1:length(x[,1])){
		j.val <- which(sum(x[j,]*2^(0:(length(x[j,])-1))) == x.val)
		m1[i.val,j.val] <- f1(x[i,],x[j,])
	}
}
m1

# 演算２。要素集合のintersection
f2 <- function(x,y){
	k <- length(x)
	tmp <- as.matrix(expand.grid(rep(list(c(0,1)),k)))

	tmp.val <- apply(t(tmp) * 2^(0:(k-1)), 2, sum)

	z <- x*y
	z.val <- sum(z*2^(0:(length(x)-1)))
	which(z.val == tmp.val)
}

m2 <- matrix(0,length(x[,1]),length(x[,1]))
for(i in 1:length(x[,1])){
	i.val <- which(sum(x[i,]*2^(0:(length(x[i,])-1))) == x.val)
	for(j in 1:length(x[,1])){
		j.val <- which(sum(x[j,]*2^(0:(length(x[j,])-1))) == x.val)
		m2[i.val,j.val] <- f2(x[i,],x[j,])
	}
}
m2

# 演算3 要素集合の非共有部分
f3 <- function(x,y){
	k <- length(x)
	tmp <- as.matrix(expand.grid(rep(list(c(0,1)),k)))

	tmp.val <- apply(t(tmp) * 2^(0:(k-1)), 2, sum)

	z <- rep(0,k)
	z[which(x+y==1)] <- 1
	z.val <- sum(z*2^(0:(length(x)-1)))
	which(z.val == tmp.val)
}

m3 <- matrix(0,length(x[,1]),length(x[,1]))
for(i in 1:length(x[,1])){
	i.val <- which(sum(x[i,]*2^(0:(length(x[i,])-1))) == x.val)
	for(j in 1:length(x[,1])){
		j.val <- which(sum(x[j,]*2^(0:(length(x[j,])-1))) == x.val)
		m3[i.val,j.val] <- f3(x[i,],x[j,])
	}
}
m3


############
# べき集合の要素の組み合わせが要素
# 2^(2^k) = K
K <- 2^(2^k)
#K <- 20
#tmp.K.list <- rep(list(c(0,1)),K)
#y <- as.matrix(expand.grid(tmp.K.list))
y <- matrix(0,K,2^k)
for(i in 2:K){
	y[i,] <- y[i-1,] + c(1,rep(0,2^k-1))
	for(j in 1:(2^k)){
		if(y[i,j] == 2){
			if(j < 2^k){
				y[i,j+1] <- y[i,j+1] +1
				y[i,j] <- 0
			}else{
				y[i,] <- rep(0,2^k)
			}
			
		}
	}
}
# べき集合に「値」を与えて、IDとする
y.val <- apply(t(y) * 2^(0:(K-1)), 2, sum)

# すべての「べき集合の要素集合」を要素とする集合同士の演算を考える
M <- matrix(0,K,K)

for(i in 1:K){
	# 第iの集合が2^k個の部分集合のどれを持っているか
	tmp.i <- y[i,]
	for(j in 1:K){
		# 第jの集合が2^k個の部分集合のどれを持っているか
		tmp.j <- y[j,]
		# 上で定義したm3の演算を、第i、第jに含まれる部分集合同士に適用すると
		# それぞれのペアについて演算f3の結果の部分集合IDが返ってくる
		tmp.m <- m3[which(tmp.i==1),which(tmp.j==1)]
		# 返ってきた部分集合IDのユニークなものを取り出して
		# それに相当mする「総数K=2^(2^k)」個の要素の集合のIDを確認する
		#tmp.val <- sum(y.val[unique(tmp.m)])
		tmp.val <- sum(2^(unique(tmp.m)-1))
		# それを演算の結果として納める
		M[i,j] <- tmp.val+1
	}
}
# このMのすべての行に単位元は存在する
# このMのすべての行に逆元は存在する？
tanni <- gyaku <- rep(0,K)
for(i in 1:K){
	if(prod(M[i,]-1) == 0){
		tanni[i] <- 1
	}
	if(prod(M[i,]-i) == 0){
		gyaku[i] <- 1
	}
}
par(mfcol=c(1,2))
plot(tanni,main = "単位")
plot(gyaku,main = "逆")