積 デカルト積 グラフのデカルト積は、の順序対をノードとして、のときにはを辺に持ち、また、のときにはを辺に持つようなグラフ # グラフ(とその隣接行列)を適当に作り 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は無向グラフのエッジをノードに置き換え、頂点をエッジに置き換えたもの(Wiki) ひとまずRでたどって処理を追ってみる # 適当にグラフオブジェクトとその隣接行列を作る g <- make.graph.adj(5) # 補助関数 # ベクトルの要素ごとにxor(),&関数を適…

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

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

ブール演算・ビット毎演算を用いて、色々な効率化・高速化アルゴリズムがある。その例が以下に挙げられている 複数の情報、を詰め込む・へばらす 2012年11月10日を20121110と表すことを考える 年が２ 年を構成する４つの数字を６桁左へシフトして 月を構成す…

２進数表記での算術演算にブール演算を使う 非負の整数xをk桁で二進数表記しよう to_bin.ry <- function(k, x){ if(k <= 0){ return(c()) } else { return(append(Recall(k-1, x%/%2), x%%2)) } } to_bin_rev.ry <- function(x){ sum(x*2^((length(x)-1):0))…

という演算はの値の取り方４通りのそれぞれに(0,1)のいずれかを対応付けることで網羅できるから、通りある 16種類の演算のそれぞれについて2x2テーブルを作ってみる boolean.op <- array(c(t(expand.grid(rep(list(0:1),4)))),c(2,2,16)) # The i-th operati…