#集合から冪集合への写像の集合でグラフを表すことにすれば，無向グラフと有向グラフ，ハイパーグラフを一つで定義できそうな。
#e : p ----> {q} という写像をp--->qというエッジと見るわけで。1:1ならフツーのグラフになり，一般ならf^-1(q) から qへのハイパーエッジをfが定義する。
#あ，向き無しエッジは勘違いしていたことに気づいた・・・・（紙で書いてるうちは気づかずキーボードで打ってると間違いに気がつく。
#( {}の逆象をとればいいかと思ったら，これはまずいのでした・・・・ )
#あれ，f:x--->{},f:y---->{],g:z---->{},g:y----->{}な写像を向き無し辺と扱おうと思って，まずいような気がしてきたけど，これでもいいような気もして。（あいまい
#上の例ではfはx----y,gはz----yな向き無し辺。この定義でいけば向き無しと向き付きが混在しているグラフが表せるような。
#（ああ，写像の定義域が違うから，「集合から冪集合への写像の集合」という定義じゃ曖昧なわけか）
#またおもしろそうなことを… 例によってイメージで話してると食い違うので、(1)yamasushiさんが考えるモデルのちゃんとした定義と(2)それがグラフなどに相当するというなら、(例だけではなく)フォーマルな形での、一般のグラフの表現へのマッピングの方法、を示してもらうといいかなあ。
#すいません。修正してみました。グラフというのはノード同士がつながってるかどうかとノード間の向きをどう決めるかなんですが，ノードに辺が付いてないときには{}を返すことにする。これでつながりがあるかどうかは区別できる。向き無し辺fはf(x) = f(y) = {x,y}なfとなります。x,y以外なら{}を返す写像が向き無し辺。
#（循環グラフはうまく表せない。） が，有向グラフと無向グラフが同じ定義に乗ることになるような。
#f:x--->{x} , (f:other--->{})の解釈をどうするかで，有向グラフだけの定義になり，有向グラフと無向グラフが混在した定義にもなる。
#仮説なんですが，「写像から冪集合への写像の集合」がグラフを統括する集合になるのではないかと。冪集合が終点を決めると考えると有向ハイパーグラフと有向グラフを包含する定義になる。(無向は入らない。) 無向グラフを考えるときには，始点の集合が終点に含まれたときの解釈になる。（後半があいまいですが・・・
#んーとそういう断片的な話ではなくて、(1)yamasushiモデルの形式的な定義 (2)普通にグラフと言われるものへのマッピング、があると議論が進むと思うんですが。形式的な定義というのは、例えば http://ja.wikipedia.org/wiki/%E3%82%B0%E3%83%A9%E3%83%95%E7%90%86%E8%AB%96 の「厳密な定義」のところにあるような形です。 #まず，有向グラフ f(e)=(n_1,n_2)とすると，g(n_1)={n_2} , g(other) ={}なgが対応するわけです。
#{n_1,n_2,....n_m}--->{nn_1,.....nn_m]なハイパーエッジは，g(n_*) = {nn_*}なgが対応するわけです。有向の場合だけならこれで統合される。
#そうじゃなくて、まずyamasushiさんが考えている構造の形式的な定義をください。でないとそっから先の議論がわからないです。
#集合Vと冪集合2^Vの写像の集合をEとする。Vの元をx,yEの元をeとするとき，e(x) = {y} e(x 以外)={}のときに，eをxからyに向かう辺とする。（こんな感じですか？
#E:V-->2^V ; E∋e ; V∋x, y ; e(x) = {y} e(x以外)=∅ なeを xからyに向かう辺とする。
#(※ eが1:1写像なら，通常のグラフになり，一般の写像であるなら，e^-1({y})からyへ向かう有向ハイパーエッジになる。
#終点が一つのハイパーグラフが定義できれば，一般のハイパーグラフはそこから導出されるんで，これで十分なのかもしれませんが・・・
#いやまあ，これだけの話なんで，すでに同じようなことは言われている予感はしまくりなんですけど。
#おお、そうそう、そういう定義がわかりやすいです。ところでe(x以外)=∅だとeは1:1写像ではないと思うんですが (Vの元が二つしかない場合を除く)、「eが1:1写像なら通常のグラフ」というのはどういうことですか。
#あー，そうか。えーとどう言えばいいのか。
#e(x) = {y} ; e(z) = {y} ; ===> x==z という意味でして，つまりyに飛んでくるノードは一つだけ。
#∅の扱いが・・・・・
#S:Vのシングルトン全体⊂2^V ; E:V-->S∪{∅} ; V∋x , y ; E∋e ; e(x) = {y} , e(x以外) = ∅ ; なeをxからyに向かう辺と呼ぶ。(より限定した定義。
#E:V-->2^V ; E∋e ; 2^V∋X,Y ; X∋x なら e(x) = Y , e(それ以外)=∅ ; なるeをXからYへ向かう辺。（一般的な定義。
#E:V-->2^V ; E∋e ; 2^V∋X ; X∋x なら e(x) = X , e(それ以外)=∅ ; なるeを頂点Xを持つ無向辺。（※ 上で言及した向き無しの場合の別バージョンの定義。
#有向と無向が同じ形式で定義できるよね？というだけの話でして・・・・
#「頂点Xを持つ無向辺」とはどういう意味ですか? 辺だから無向であっても頂点は二つ必要だと思うのでちょっと混乱。
#Xは冪集合の元です。
#それはわかるけど、「eをXからYへ向かう辺」と言ってるのはXやYをそれぞれひとまとめで頂点とみなしてるんじゃないんですか?
#向き付きだけ考える場合なら，Xが始点側，Yが終点側ということになります。向き無しの場合は形式は似ているのですが，別物で集合Xのメンバーシップ関数と同じ働きをするわけです。
#形式は同じなんですが，意味が異なっているという。で，「循環しない」という条件をつけるなら，向き無しと向き付きを混在できるなーと。
##ああなるほど。「循環しないという条件」て要するにDAGってことですよね。で、DAGとして解釈する場合と無向グラフとして解釈する場合では意味の付け方が違うと。そこまではわかった気がします。
#向き無しの時の定義にはまだ無理がありますね。・・・向き付きはこれで良さそうな感じなんですが。どうもメモに書いてる内には気づかないことが多いのでして。（汗
#まあ，終点側が一つだけのハイパーエッジで向き無しは表現できるわけですが・・・・・
#syntax-rules のマクロを生成するマクロで再帰できないみたいです:
#(define-syntax bar
(syntax-rules ()
((_ args ...)
'(bad args ...))))
(define-syntax foo
(syntax-rules ()
((_ xs)
(letrec-syntax ((bar
(syntax-rules ()
((_ (%x . %xs) %ys)
(bar %xs (%x . %ys)))
((_ () %ys)
'%ys))))
(bar xs ())))))
(foo (x y))
;; => (bad (y) (x))#期待する結果は (y x) です。
#既知のバグですね。 私も何度か引っ掛かったことが…。
#ああ、そんな気はしてました。
Gauche > Archives > 2014/11/11