補グラフ:グラフ代数

• ぱらぱらめくる『クヌース本4.0』から
• 補グラフ
  • ,
    • 
    • それぞれの隣接行列をとする
  • ,ただしは要素がすべて1の正方行列、は単位行列。は完全グラフの隣接行列
  • ブール代数っぽく、隣接行列をTRUE,FALSEにしてやってみよう
  • 補グラフを作ることは、隣接行列のブール反転して対角成分だけ少しいじればよい

make.graph.adj <- function(n,r=0.3,directed = FALSE){
	m <- matrix(sample(c(FALSE,TRUE),n^2,prob=c(1-r,r),replace=TRUE),n,n)
	if(!directed){
		m <- m | t(m)
		diag(m) <- FALSE
	}
	library(igraph)
	if(directed){
		g <- graph.adjacency(m,mode="directed")
	}else{
		g <- graph.adjacency(m,mode="undirected")
	}
	
	plot(g)
	return(list(m=m,g=g))
}
g <- make.graph.adj(8)

graph.complement <- function(m,diag.zero=TRUE){
	new.m <- !m
	if(diag.zero)diag(new.m) <- FALSE
	new.m
}
compl.m <- graph.complement(g$m)
compl.m | g$m

• • boolで隣接行列

> g
$m
      [,1]  [,2]  [,3]  [,4]  [,5]  [,6]  [,7]  [,8]
[1,] FALSE  TRUE  TRUE FALSE FALSE  TRUE  TRUE  TRUE
[2,]  TRUE FALSE FALSE FALSE FALSE  TRUE FALSE FALSE
[3,]  TRUE FALSE FALSE FALSE FALSE  TRUE FALSE FALSE
[4,] FALSE FALSE FALSE FALSE FALSE FALSE  TRUE  TRUE
[5,] FALSE FALSE FALSE FALSE FALSE  TRUE  TRUE  TRUE
[6,]  TRUE  TRUE  TRUE FALSE  TRUE FALSE  TRUE  TRUE
[7,]  TRUE FALSE FALSE  TRUE  TRUE  TRUE FALSE FALSE
[8,]  TRUE FALSE FALSE  TRUE  TRUE  TRUE FALSE FALSE

$g
IGRAPH U--- 8 14 -- 

> plot(g$g)