グラフ代数

積:グラフ代数

積 デカルト積 グラフのデカルト積は、の順序対をノードとして、のときにはを辺に持ち、また、のときにはを辺に持つようなグラフ # グラフ(とその隣接行列)を適当に作り g1 <- make.graph.adj(5) g2 <- make.graph.adj(4) gr.dec.prod <- function(m1,m2){ n…

和:グラフ代数

和 直和 結び 有向結び 和の法則 , , , , X <- matrix(c(0,1,1,1,0,0,1,0,0),byrow=TRUE,3,3) Y <- matrix(c(0,1,1,1,0,1,1,1,0),byrow=TRUE,3,3) sum.graph <- function(X,Y){ dimX <- dim(X) dimY <- dim(Y) Z <- matrix(0,dimX[1]+dimY[1],dimX[2]+dimY[2…

線グラフ(line graph)からハイパーグラフへ:グラフ代数

グラフと線グラフとについて前記事に書いた 要素集合があったとき、 いわゆるグラフのノードは個々の要素 いわゆるグラフのエッジは個々の要素のペア 線グラフのノードはいわゆるグラフのエッジに対応して、それは要素のペア 線グラフのエッジはいわゆるグラ…

線グラフ(line graph):グラフ代数

Line graphは無向グラフのエッジをノードに置き換え、頂点をエッジに置き換えたもの(Wiki) ひとまずRでたどって処理を追ってみる # 適当にグラフオブジェクトとその隣接行列を作る g <- make.graph.adj(5) # 補助関数 # ベクトルの要素ごとにxor(),&関数を適…

補グラフ:グラフ代数

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

ぱらぱらめくる『クヌース本4.0』

The Art of Computer Programming,Volume 4, Fascicle 0 Introduction to Combinatorial Algorithms and Boolean Functions 日本語版 (ASCII Addison Wesley Programming Se)作者: Donald E. Knuth,和田英一出版社/メーカー: アスキー・メディアワークス発売…