2012-01-01から1年間の記事一覧
要素があるときに、集合族を考えて、さらにその中で複体制約を満足することを考える さらに、複体であって、がすべて複体を構成する単体に帰属するものとする その個数はこちらに書いたように、数列ID:A006126 "Number of hierarchical models with linear t…
xは行の真偽値表(２列) library(igraph) bzdd <- function(x,type="zdd"){ v <- c(x) K <- log(length(v),2) # グラフに描くときに、判断分岐の高さごとにy軸座標を与えたいので、その値 lay.y <- c() for(i in 1:K){ lay.y <- c(lay.y,rep(i,2^(i-1))) } # …
置換集合向けの決定木ダイアグラムpiDD 資料１ 資料２ BDD/ZDDは組み合わせ集合の空間の部分をうまく表現する仕組み BDDの構成アルゴリズム BDDをべたべたにRで書いてみようこちら piDDは置換(順列)の集合の空間の部分をうまく表現する仕組み(らしい) ルービ…
目次 I Graphs II Hypergraphs I Graphs 1. Basic Definitions and Concepts 2. Trees and Bipartite Graphs 3. Chordal Graphs 4. Planar Graphs 5. Graph Coloring 6. Traversals and Flows II Hypergraphs 7. Basic Hypergraph Concepts 8. Hypertrees an…
Chap 7 ハイパーグラフの基礎概念 基礎の基礎 Vertices Hyperedges (Vertidesセット) 隣接は、同様のものの間の関係(Vertices間、Hyperedges間) Hyperedgesの隣接 VeritexとHyperedgeとの関係「Incident」 次数：ノードの次数、エッジの次数 Incidence とDua…
グラフに関しては、ごく普通の記載
Introduction to Graph and Hypergraph Theory作者: Vitaly I Voloshin出版社/メーカー: Nova Science Publishers発売日: 2009/05/13メディア: ハードカバー クリック: 3回この商品を含むブログを見る こちらでハイパーグラフについてかじったハイパーグラフ…
積 デカルト積 グラフのデカルト積は、の順序対をノードとして、のときにはを辺に持ち、また、のときにはを辺に持つようなグラフ # グラフ(とその隣接行列)を適当に作り 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 (2) 日本語版 Seminumerical algorithms Ascii Addison Wesley programming series作者: Donald E.Knuth,有沢誠,和田英一,斎藤博昭,長尾高弘,松井祥悟,松井孝雄,山内斉出版社/メーカー: アスキー発売日: 2004/10メディア: …
The Art of Computer Programming,Volume 4, Fascicle 0 Introduction to Combinatorial Algorithms and Boolean Functions 日本語版 (ASCII Addison Wesley Programming Se)作者: Donald E. Knuth,和田英一出版社/メーカー: アスキー・メディアワークス発売…
という行列の積はである。この演算にはとが出てきている。この２つの二項演算を「他の二項演算」にも開放しよう、というもの "行列の積の一般化"(クヌース本1.1のp12では"一般化行列積"となっているのだが、generalized matrix multiplicationともちょっと違…
今日のMIKU 単体・複体を用いた組合せ論から、単体の体積計算 次元を一つずつ上げていく が出てくるけれど、その成分の多くはキャンセルアウトされる 尖った図形なのでその体積は次元とともに急速に小さくなる その小さくなり方は球体積の小さくなり方より急…
The Art of Computer Programming Volume 1,Fascicle 1:MMIX―A RISC Computer for the New Millennium日本語版 (Ascii Addison Wesley programming series)作者: ドナルド・E.クヌース,Donald E. Knuth,有澤誠,青木孝,和田英一出版社/メーカー: アスキー発売…
Rで簡単に画像を扱う形式にppm形式というのがある ライブらるpixmapをインストールするとppm形式の画像を読み込む関数read.pnm()がある x <- read.pnm(system.file("pictures/logo.ppm", package="pixmap")[1]) plot(x) print(x) 読み込んだオブジェクト x …
こちらでBDDのことをやっていて、Primitiveな配列というものが出てきた ある長さLの配列がn個(複数)あって、それらをタンデムにつないで、長さが２倍の配列(長さ2L)を作るときのこと 連結するにあたって、同じものを組み合わせないで作る配列が「長さ2LのPri…
ZDD:ゼロ抑制BDD 組合せ論で力を発揮する に行きつく経路が多いときに有用である BDDと違う点 節点の解釈が違う 終点ははないこともある 節点からの２本のエッジが同一のノードに接続することもある 節点数が節約されることがある BDDではノードが「Primitiv…
昨日の続き 二分決定図 BDD グラフ状 ノードとエッジがある ノードからは２本のエッジが出る(特別な２つのノード,を除く エッジには２種類ある ノードから出る２本のエッジは２種類が１本ずつ ノードには１本以上のエッジが入る(１つのルートノードは例外で…
ブール演算・ビット毎演算を用いて、色々な効率化・高速化アルゴリズムがある。その例が以下に挙げられている 複数の情報、を詰め込む・へばらす 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…
MMIX 16通りのブール演算 ビット毎演算 ブール演算のビット毎の演算のテクニック BBD
BDD,ZDDのことを書いた(こちら) クヌース先生の以下の本で扱っているという The Art of Computer Programming Volume 4, Fascicle 1 Bitwise Tricks & Techniques; Binary Decision Diagarms 日本語版 (ASCII Addison Wesley Programming Se)作者: Donald E.…
Recall()関数というのを教えてもらった # Recall()を使う ## A trivial (but inefficient!) example: fib <- function(n) if(n<=2) { if(n>=0) 1 else 0 } else Recall(n-1) + Recall(n-2) fibonacci <- fib; rm(fib) ## renaming wouldn't work without Rec…
