積:グラフ代数

R 組合せグラフ代数ブール演算

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

2012-11-19

和:グラフ代数

R 組合せグラフ代数ブール演算

和直和結び有向結び和の法則 , , , , 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…

2012-11-19

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

R 組合せグラフ代数ブール演算

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

2012-11-19

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

R 組合せグラフ代数ブール演算

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

2012-11-19

補グラフ:グラフ代数

R 組合せグラフ代数ブール演算

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

2012-11-17

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

R ぱらぱらめくるシリーズ組合せグラフ代数ブール演算パズル囲碁 Satisfiability SAT 制約充足問題 Constraint satisfaction problem CSP

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