#公約数があればつながっているというルールで、どんなグラフも素数の積で表せそうな気がするのですが、気のせいでしょうか。三角形{p,pq,pr}、隣接する三角形{p,spq,prs,s}のように、適当な頂点に素数をひとつ割り当てていくという。エッジに相当するのが公約数。
#何となく言わんとしてるところはわかるんですが、もうちょい説明してください。前提(やりたいこと)、方法、得られる結果、等
#やりたいことは人間関係を表す簡単な方法で、人間に素数の積を割り当てるわけです。ある人間の積と公約数を持つ集団は直系となる。兄弟か両親。
#もうちょい詳しく。
#私が今まで理解した範囲からすると、(1)グラフの各エッジにユニークな素数を割り当て (2)頂点はそこに接続する各エッジの素数の積とする、と言いたいのかなと想像したんですが、違いますか。
#各頂点にユニークな素数を割り当てるのですが、頂点の識別にはつかわないわけです。その素数が公約数(つまりエッジ)になるような頂点をつけるためです。頂点とエッジという考えでなく、つながりのルールしかない。識別として素数の積を使う。素数の性質上これは一意だからです。
#三角形{p,pq,pr}にpに頂点をひとつつけるとき、新たに素数を生成しsとする。そして{p,pq,pr,sp}を得る。
#もともとの目的は家系図をどうあらわすかで、父方の祖父・祖母をt,uとし、母方の祖父・祖母をv,wとする。{t,u,tup,tur}が父方。{v,w,vwq,vws}が母方。{tup,vwq,pqa,pqb,pqc}が自分の家族。というふうに表せる。
#兄弟は両親の「成分」の積を公約数として持つわけです。親と自分は親の「成分」素数を公約数として持つ。
#親族関係を覚えられないのでどうしたものかと考えたという。
#言ってることが矛盾してるのでわからないのです。「各頂点にユニークな素数」と言っていながら、「三角形{p,pq,pr}」では後ろ二つの頂点は素数じゃないですよね。もういちどゼロから、矛盾のない定義を教えて頂けますか。
#あと「頂点とエッジという考えでなく」というのもわからない。別の用語を使ったとしても、一般にグラフというのは
#「頂点とエッジとその関係の集合」と同型になるはずです。なので、一般的な用語で説明しても問題ないはずです。もしそういう形で表せない構造を考えているなら、その定義も教えてください。
#ちょっと訂正。エッジというのは頂点間の関係にすぎないので、「頂点とエッジの集合」だけでいいですね。
#もしかして連結された集合を考えてるのかな。要素がいっぱいあって、ある特性で(重なり合う)部分集合に分割できるような関係。
#おっけー、わかった気がします。表現したいのは有向非循環グラフ。各ノードはユニークな自然数を持つ。まず流入の無いノードに素数をそれぞれ割り当てる。次に、上流のノードの値が全て決まっているノードについて、そのノードの値を「上流ノードの値の積」×「新たな素数」とする。と、こうですか。
#ノードの値は根基(素因数の重複を除いたもの)でもいいのかな? 公約数だけを見るなら。
#向きは付けられないですが、循環の表現については考えてませんでした。実例を補足すると、三角形{a,ab,ac}にdをつなげる場合、完全グラフ{a,ab,ac,ad}、隣接する三角形{ad,ab,dac,d}、三角形と線{da,ab,ac,d}となります。つまり、頂点を追加するとグラフの数も変動します。
#えーと、家系図は非循環グラフで描かれますが、わたしの上の表現では循環グラフです。
#すいません。循環の意味がちょっとまちがえてるかも。(汗
#む、私の仮説よりもうちょい複雑なようですね(私の提示したモデルだと循環があると値が決まらないので)。上のyamasushiさんのポストでわからないのは(1)「dをつなげる、とはどういう操作か、つながった後は何になるのか(2)完全グラフとは何か(3)三角形{ad,ab,dac,d}tte
#って点が四つあるようだけどどうして三角形? (4)「グラフの数」とは? 単一のグラフではなくグラフの集合の話をしているの? ってあたりです。
#(4)グラフの数というのは舌足らずでした。ノードの根基が変わるという意味です。(2)完全グラフというのはどのノードともつながっているという意味です。つまりどのノードとも公約数がある。
#ああ、つまり今考えているグラフの中に、部分完全グラフとして{a,ab,ac,ad}がある、ということですか?
#ん、上の説明だと{a,ab,ac}にdを付け加える時にadとかdacとかいうノードも現れるってこと?
#整理しますと、根基の集合があるときに公約数があればつなぐということにすればグラフがかける。逆にグラフがあるとき、適当な一点からはじめて根基の集合をつくることができるということです。
#「根基の集合→グラフ」は自明ですが、「任意のグラフ→根基の集合」についてはちょっと直感的にわからないので、具体的なアルゴリズムを示してもらえるとうれしいです。
#その簡単な生成方法が三角形にノードを追加する例です。
#えーと、ノードをひとつ追加したときに、d, ad, dacという三つの数が出てきたんですが、その関係を説明してもらえますか。
#横から失礼。グラフ→根基の集合を求めるのは、こんなアルゴリズム?
#任意のグラフが与えられた時に、
#(1) 各ノードとエッジに対して異なる素数を割り当てる
#(2) 各ノードごとに、(1)で割り当てたノードの素数と、つながっているエッジの素数をすべてかけあわせる。これを根基とする
#(3) 各ノードごとに計算した根基で集合を作る
#ノードが２つなら{p,pq}、ノードが３つなら{ac,bc,bd}(団子のようにつないだもの)、{a,ab,ac}(三角形)です。
#ノードが４つなら、三角形にどうつなぐかになるのですが、それが上の例。
#あ、団子にどうつなぐかもありますね。
#わたし、アルゴリズムの形に展開できないのでうまく伝わってないような。(汗
##koguroさんのアルゴリズムはいけますね。私が最初に言った「エッジに素数」とほぼ同じ。わからなかったのはyamasushiさんのアルゴリズムです。
#でもたぶん今のでわかった。
#たぶん、表現によっては効率の良い悪いがでてくるようなきがするのですが、そこのところはわからないです。
#巨大なグラフを処理するときに一様なサイズの根基に収める必要が出てくるはずで。
#yamasushiさんので直感的に気になるのは、グラフではどのノードも対等なのに値が非対称に見えることで、まあ何となく動く気はするのだけど消えてしまう非対称性がどっかにしわよせになって病的なケースがあったりしないかなあってとこです。
#小さい素数と大きい素数を使い分ければいいような気はしますが、わたしの想定している用途は小規模なので・・・・・
#まあどんな無向グラフでもエッジに適切に方向を定めてやればDAGにできるんだし、対称なグラフの表現が非対称であったとしてもおかしなことではないか。
#ちなみに、エッジに素数を割り当てる方法やkoguroさんの方法では、ノードの値を素因数分解すればいくつのノードにつながってるかわかるとか、koguroさんの方法ではさらに(元の素数とノードの対応を持っておけば)相手のノードもわかるとかあるんですが、yamasushiさんの方法だと全部のノードを見ないとどれにつながってるかわからないケースがありますよね ('a' だけのノードを最初に見ている場合)。それに比してメリットが思いつかないので、何でそうするかな、という感じも少しします。
#たとえば、背番号として使いつつネットワークも表現できるのですが、全体を見なければそのつながりはわからない。
#ふむ。全体をみないとわからない、という性質が必要なのですか?
#必要というか、おもしろいなあと。
#m個の鍵のうちn個以上が揃ったら開けられる、みたいなノリかな。
#人間関係にとても近いように感じたわけです。周辺の背番号との関係はわかる。しかし全体の関係はわからない。
#ああ、話がつながりました。なるほど。
#両親か兄弟かさえわからない。(笑
#あ、両親か兄弟かはわかるか。
#yamasushiさんの方法は既存のエッジを消す時に当事者以外のところに影響が波及する場合があるな。1hopだけで済みそうではあるが。
Gauche > Archives > 2014/03/15