#グラフのノードが増える一方の場合、グラフのノードが減るかもしれない場合、・・・グラフの動的な性質に応じた数列があるような感じです。たとえば、Gaucheのコミッタという資格に素数gを割り当てる。すると、gをかければコミュニティに参加できるし、割ればコミュニティから脱退する。一方、「口利き」による参加という形式がある。{p},{q}から{p,pq}のようにノードの成分をかける参加方式。{p,q,pq}のような関係もある。
#くわしくないので憶測ですが、素数の生成や公約数の計算は高速にできるし、並列計算とも相性がいいような気がする。(なんとなくですが。
#暗号処理に最適化されたCPUがあると聞いたので・・・・・
#yamasushiさんの記述でもうちょい整理したらいいかなというのが、「素数を何に割り当てるか」というところで。「Gaucheのコミッタという資格に割り当てる」というような方針がはっきりあればそれはそれで良くて (完全部分グラフ(クリーク)ごとに素数を割り当て、各ノードはそれが属するクリークの素数の積*自分のユニーク素数、とする)、すっきりするんですが
#今のアルゴリズムだと、ノードを特定する素数と関係を特定する素数が混ざっててややこしい感じなんですよね。{a,ab,ac}というネットワークの場合、aが最初のノード特定と関係の両方に使われていて、それが操作を必要以上に複雑にしているような。
#いやまあ感覚的な話ですが。x,y,zを自然数として、{x,y,z}がクリークを成していた場合に、「その関係を解消するには公約数で割る」と単純には言えない。「公約数が自分と一致している場合」だけ特別扱いすればいいけど、そういう特別扱いがちょっと美しくないな、と。
#ノードを特定する数なんですが、周囲との関係を知らなければ自分の特徴を表す数を知ることができないという性質をもつグラフの表現法になっているみたいなんです。で、昨日は向きをつけられないと書いたのですが、{ap,bp}(a<b)ならap--->bpというふうにすれば向きを付けられます。公約数は接続、公約数で割った商は向き。ということになる。とはいえ、どんな有向グラフでも表現可能かどうかはわからないです。
#周囲と関係していない孤立したノードがコミュニティに参加するときにどのような参加方法があるか？ みたいな。{p},{ga,gb,gc} ---> {gp,ga,gb,gc} もしくは {pabc , ga , gb ,gc }。
#「周囲との関係を知らないと～」はkoguroさん方式で自ノードのユニーク素数を保存しておかなければ同じことだと思います。yamasushi方式でも、結局はノードごとに素数を割り当てないとならないわけですし。
#{p,q,pq}のように割り当てる必要がない場合もあります。
#あと、{ap,bp}(a<b)ならap->bp、とするなら循環グラフは表現できなくなる気がしますし、逐次にノードを追加する方法だと矛盾無くやるのは難しい気がします。最初に与えられたグラフに対して数を振ってくならもしかするとできるかもしれませんが。
#>yamasushi そのケース考えたんですが、{p,q,pq}は p - pq - q って一直線につながってるんですよね。そこでpとqをつなげるときはどうするんですか。
#そのときには素数を割り当てるしかないですね。{cp,cq,pq}
#その「素数を割り当てるしかない」ってことは、対称となるpとqを見ているだけではわからないですよね。一般化しようとすると結構場合分けが大変になるような気がするんですが。
#ですから、表現方法によってグラフの性質が異なるわけです。基礎になる形式は同じですが。
#似たような例として、目の前にpと言うノードとqというノードが見えてて、それぞれどっかにつながってるんだけど、このpとqにつながるノードを作りたい、という場合に、単純にpqとするわけにいかない (既にpqがあるかもしれないので)。ここでも場合分けが発生しますよね。
#いっぺん、既にn個のノードがある状態で、二つのノードa_kとa_l (それぞれ自然数) の間をつなぐアルゴリズムを一般的に書き下してみたらどうなるか興味あります。特殊ケースをより分けてゆくと結構複雑になるんじゃないかと思うんですが、どうでしょ。
#もちろん、エッジを追加する時には常に新たな素数を割り当てる、とすれば簡単に出来ますが、それなら私が最初に提案した方式と変わらないですし。
#なるほど、つまり接続するにはどうするか？という点がポイントなんですね。
#あと、循環グラフが表現できないことがわかるなら、この表現で表せば循環しないということになりますよね。
#それだけがポイントではなくて、「yamasushi方式とは何か」をちゃんと説明するには、少数のノードでの具体例だけではなくて、「一般的なグラフが与えられた時にどう構成するか」とか、必要ならば「既にyamasushi表現が与えられたグラフにエッジやノードを足したり引いたりする時は一般的にどうするか」っていうのが知りたいわけです。問題の性質によっては「グラフ全体に一度に表現を与える場合のみ考えて、動的な変更は考慮しなくてよい」というケースもあるでしょうが。
#例えばkoguro方式とかは、そういう一般的な操作が直感的にわかるんですが、yamasushi方式だと一般化した時に何をどうするかがいまいち見えないので。もし「ノードユニークな素数とかエッジユニークな素数というのは不要」ってなったらそれはそれでおもしろい性質だと思うんですが。
#もしかして「グラフ内の各クリークに素数を割り当てて、ノードをそれが属するクリークの素数の積」でいいんだろか。これだと区別できないノードが出ると前は思ったんだけど、重なるクリークも許せば、各エッジは全てノード数2のクリークなんで、全てのノードは異なる値を取るはず。
#s/重なるクリーク/完全に包含されるクリーク/
#で、それだけだとエッジに素数を振るのとどう違うのってことになるんだけど、この状態から「ノードの区別が出来る限りにおいて、他のクリークに完全に包含されるクリークを除いてよい」ってやってったら最終的にyamasushi方式みたいな感じにならないかな。
#こうすると、ノードユニークな素数もエッジユニークな素数も無いけれど、各ノードは別の値を持ち、接続関係が公約数で表現されることになりそうな。
#例えばノード3つで3角形になってる場合、クリークは4つ(3ノードのが1つ、2ノードのが2つ)。それぞれ素数p,q,r,sを割り当てると、{pqr,prs,psq}。このうち1つは除ける。例えばsを除いて{pqr,pr,pq}とか。うーん、包含されるクリークにも意味を持たせようとすると「任意のものを除ける」というのはちと扱い辛いかな。
#たしかに、エッジとノードという考えよりは、クリークの合成という考えに近いみたいです。{ab,ac,a}というクリークを図示するときにはエッジにaと打つよりは三角形の内部にaと打つほうが適切。
#あと、koguro方式で積の要素の最小素数(or 最大素数)をノード固有の素数という約束にすればいいのではないかと。
#表現法の違いは集合から要素を取り除いたら結合はどうなるか？で分類できそうな気はします。{a,ab,ac}だったら一つとりのぞいてもクリークのまま。{ab,ac,cd}だと一つとりのぞくとつながらなくなる。
#あ、acをとりのぞいたら、でした。
Gauche > Archives > 2014/03/16