正方形のタイルで平面を埋め尽くすのはタイリングの一種 正三角形のタイルで平面を埋め尽くすのもタイリングの一種 正三角形は正単体の一つ 正単体での埋め尽くし・タイリングとは？ 頂点数２の正単体が１次元空間でタンデムに並んでいるのは、１次元空間の…

こちらから ベクトルとその演算の半分くらいを習ったところ ２より大きい整数が素数であるかの判定 # xを2,3,...,(x-1)で割って、あまりを調べる x <- 17 waru <- 2:(x-1) waru amari <- x%%waru amari # あまりがすべて0ではない # あまりが0 zerodesuka <-…

前の記事でCUDDの実行確認をしてみた。そこではnanotrav.exeを動かして、hoge.blif ファイルを読んでいる nanotrav,blifってなに？ blifフォーマットはこちらにあるように"logic-level hierarchical circuit in textual form"なのだという nanotravについて…

サンプルファイルとか転がっていないだろうか… こちら こちら hello のサンプルをまずは…(こちら) gcc sample1a.c -o sample1a とやるも『アクセスが拒否されました。』と… こちらにあるようにgccは「影」でgcc-3.exeが本物なので gcc-3 sample1a.c -o sampl…

/* LINTLIBRARY */ #include "util.h" #ifdef BSD #include <sys/types.h> #include <sys/time.h> #include <sys/resource.h> #if 0 #define etext _etext #define edata _edata #define end _end #endif extern int end, etext, edata; #endif void util_print_cpu_stats(FILE *fp) { #if 0 struct ru</sys/resource.h></sys/time.h></sys/types.h>…

# $Id$ # # Makefile for the CUDD distribution kit #--------------------------------------------------------------------------- # Beginning of the configuration section. These symbol definitions can # be overridden from the command line. # …

CUDDのパッケージをとって来よう ホームパージ 圧縮ファイル Windowsでmakeやgccを動かすためにCygwinを入れよう Cygwinを入れるとLINUXコマンドがWindowsのコマンドプロンプトで動くようになる！のですね(こちらやこちら) Cygwinを入れるのもずいぶん久しぶ…

昨日、ZDDでクリークを列挙する話を書いた グラフ情報(隣接関係の情報)からクリークを列挙するのは大変だ その大変さは、0/1のべき乗をZDD化するより、グラフ情報からZDD化する方が難しい(らしい)ことと関係しそうだ 超立方格子上の点のハミング距離に適当に…

ZDDについて勉強中 グラフのクリークの演算がありそうなCUDDというのがある PDF ダウンロードなどのサイト ダウンロード用圧縮ファイル置き場が見つかりにくいけれど... こちら PDFにある記載 Graph operators Cudd_zddCliques: Finds the set of all clique…

ファイルの書き出しでエンコーディングの指定はfileEncoding=""というようなデフォルト指定になっている デフォルトはgetOption("encoding")のようにしてとってくる コンピュータが使っているエンコーディングをRの中でも使うのがデフォルトで、Rの中で使う…

今日(20121121)のMIKU 第一の話題は確率収束 確率変数が概収束することと確率収束すること 値が収束することと、確率が収束することの違い 悉皆と、たとえ、ときどきに例外があっても、それが確率に反映しないくらい、定義域密度が小さければ(有理数が実数の…

要素があるときに、集合族を考えて、さらにその中で複体制約を満足することを考える さらに、複体であって、がすべて複体を構成する単体に帰属するものとする その個数はこちらに書いたように、数列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 単体・複体を用いた組合せ論から、単体の体積計算 次元を一つずつ上げていく が出てくるけれど、その成分の多くはキャンセルアウトされる 尖った図形なのでその体積は次元とともに急速に小さくなる その小さくなり方は球体積の小さくなり方より急…