グラフ理論の問題を出し合うスレ

**名無しさん＠お腹いっぱい。** · 2006/08/19(土) 17:36:22

面白い問題ｷｳﾞｫﾇ

**名無しさん＠お腹いっぱい。** · 2006/08/19(土) 21:11:41

SUBGRAPH について教えてください．

**名無しさん＠お腹いっぱい。** · 2006/08/20(日) 22:57:36

>>2
部分グラフ
点集合Vと辺集合EからなるグラフG=（V,E)の
部分グラフは　G=（V',E') （V'⊆V、E'⊆E）

**名無しさん＠お腹いっぱい。** · 2006/08/25(金) 01:32:17

それだけでは定義できんのでは？
E'はV'に無関係には選べんだろ

**名無しさん＠お腹いっぱい。** · 2006/09/09(土) 10:00:21

>>4のいいたいことが分からない

**名無しさん＠お腹いっぱい。** · 2006/09/09(土) 10:25:09

e∈E' のとき e の端点は V' に入ってないといけない

3 · 2006/09/10(日) 03:50:05

うん、そうだったね
>>3は無しで
正しい定義はここに書くにはスペースが足りないようだ

**名無しさん＠お腹いっぱい。** · 2006/10/08(日) 06:57:26

微妙にスレ違いｽﾏｿ。
ランダムグラフで各ノードがリンクのあるノードとのみ情報交換できる状態で
自律分散的にクリークを構築するアルゴリズムってなんかあるかな？

**名無しさん＠お腹いっぱい。** · 2006/10/08(日) 09:34:36

簡単だ
枝はクリークじゃないか

**名無しさん＠お腹いっぱい。** · 2006/10/08(日) 11:03:56

>>9
いや、そうなんだけど・・・
可能な限り構成ノード三個以上、むしろ構成ノードが多いクリークでって
制約では？

**名無しさん＠お腹いっぱい。** · 2006/10/11(水) 18:58:58

自分の隣人に、それぞれの隣人リストを送ってもらって、
自分でクリーク作るしかないんじゃない？

**名無しさん＠お腹いっぱい。** · 2006/10/22(日) 21:37:03

boost::graph
って専門の人からみたらどうなのでしょうか？

**名無しさん＠お腹いっぱい。** · 2006/10/23(月) 05:59:07

LEDAが高いからなぁ

**名無しさん＠お腹いっぱい。** · 2006/11/11(土) 22:22:17

教えて君です。グラフ理論とベクトルとJavaをつなぐいい本があったら
教えてくださいです。

**名無しさん＠お腹いっぱい。** · 2006/11/11(土) 23:06:13

http://www.google.co.jp/search?num=20&hl=ja&q=%E3%82%B0%E3%83%A9%E3%83%95%E7%90%86%E8%AB%96+%E3%83%99%E3%82%AF%E3%83%88%E3%83%AB+Java+site%3Aamazon.co.jp&btnG=Google+%E6%A4%9C%E7%B4%A2&lr=lang_ja

**名無しさん＠お腹いっぱい。** · 2006/11/23(木) 00:13:48

電車で都内周りまくって
元の位置に戻ってきて到着駅数が最大になるのは、どんなルートだい？

**名無しさん＠お腹いっぱい。** · 2006/11/23(木) 09:59:01

LONGEST CYCLE問題。NP完全問題

**名無しさん＠お腹いっぱい。** · 2006/11/24(金) 08:38:33

NP「完全」じゃないだろ

**名無しさん＠お腹いっぱい。** · 2006/12/01(金) 01:11:33

新聞の番組表は区切りごとに、ry)…何色あれば塗れるんかね？

**名無しさん＠お腹いっぱい。** · 2006/12/06(水) 23:18:07

平面で飛び地がなければ4色だな
http://ja.wikipedia.org/wiki/%E5%9B%9B%E8%89%B2%E5%AE%9A%E7%90%86

**名無しさん＠お腹いっぱい。** · 2006/12/07(木) 10:49:32

グリッドグラフでも三彩色不可能なの？

**名無しさん＠お腹いっぱい。** · 2006/12/20(水) 00:44:01

　　　　A-TV　7:00-8:00, 8:00-9:00, 9:00-10:00
　　隣のB-TV　7:00-7:30, 7:30-8:30, 8:30-10:00
その隣のC-TV　7:00-10:00
とすると、B-TVとA-TVの関係から、B-TVの番組表を塗るには必ず３色必要。
なので、C-TVを塗るには４色目が必要。よって４色以上必要。　

**名無しさん＠お腹いっぱい。** · 2007/01/16(火) 08:40:00

区切り用に黒、塗りつぶし用に白があれば十分

**名無しさん＠お腹いっぱい。** · 2007/02/28(水) 22:39:00

交差点が存在するグラフを、交差点が存在しないように変換するアルゴリズムてありますか？

**名無しさん＠お腹いっぱい。** · 2007/03/01(木) 02:29:43

交差点って何？平面グラフでないってこと？

**名無しさん＠お腹いっぱい。** · 2007/03/02(金) 10:23:50

平面グラフの平面描画を得たいという話ならいくらでもある

**名無しさん＠お腹いっぱい。** · 2007/03/06(火) 13:15:09

隣接行列の固有値ってどんなことに使うんですか？

**名無しさん＠お腹いっぱい。** · 2007/03/11(日) 15:33:31

GoogleのPageRankを算出する時とか

**名無しさん＠お腹いっぱい。** · 2007/04/04(水) 06:22:57

>>5
E'はV'の元を結んで構成されるとして、E'の元はEにもあるってことだろ？
それが部分グラフですよって。

多分ＪＲの両毛線みたいなローカルな話がしたかったんだろ。

**名無しさん＠お腹いっぱい。** · 2007/05/19(土) 01:17:49

誰か，Cayley Graphの詳しい定義を教えて下さい．
いくつか，本を読んだのですが，
詳しく書かれていなかったり，理解できませんでした．

**名無しさん＠お腹いっぱい。** · 2007/05/27(日) 18:26:48

G=(V,E)を連結無向グラフとする。Gの任意の極小カットセットはカットであることを示せ

上の問題を自分なりに考えてみました。
どなたか合っているかどうか確かめてくれると嬉しいです。

Gの任意の極小カットセットFはその性質から、そのどの真部分集合F'もカットセットではない。
ここで、任意のf∈Fを選びG'=(V,E-(F-f))とすると、上の性質よりG'はまだ連結となっている。
このG'から改めてfを除くとG'は二つの連結成分にわかれ、それぞれの連結成分の点の集合を
V1,V2とするとGはV1とV2お生成部分集合に分かれる。
よって、G=(V,E)を連結無向グラフとする。Gの任意の極小カットセットはカットである

**名無しさん＠お腹いっぱい。** · 2007/05/30(水) 23:46:46

グラフマイニングのためのツールを教えなさい

**名無しさん＠お腹いっぱい。** · 2007/06/07(木) 16:46:22

グラフとは何か答えなさい

**名無しさん＠お腹いっぱい。** · 2007/10/14(日) 20:49:51

誰か深さ優先探索を用いた有向グラフの強連結成分分解を分かりやすく教えてちょんまげ

**名無しさん＠お腹いっぱい。** · 2007/11/09(金) 05:09:24

クラトウスキーの定理の証明ってどのくらい難しいですか？

**名無しさん＠お腹いっぱい。** · 2007/11/12(月) 17:31:12

star factor の意味を教えてください。
よろしくお願いします。

**名無しさん＠お腹いっぱい。** · 2008/02/23(土) 17:33:43

初心者な質問で申し訳ないですが、グラフ理論において平均距離とは、すべての経路長を１として到達にかかった長さ、または経由したノード数の数という認識でよろしいのでしょうか？

**名無しさん＠お腹いっぱい。** · 2008/02/23(土) 17:35:40

↑訂正です。
経路長の平均もしくは、経由したノード数の平均
でした

◎韓 · 2008/02/24(日) 03:40:00

マルハン王国の闇http://jbbs.livedoor.jp/bbs/read.cgi/game/1733/1086581896/3-8

韓会長は月に一度は韓国へ里帰りしていた。しかし理由はそれだけではなかった。
伊藤忠商事本社イケダ部長と駐韓ソウル支店長と共に新韓銀行本店、新韓生命保険本社へ通った。なぜ韓国マネーとつながりがあるか？

多店舗で展開する場合は方法に問題がある。各店舗ごとに用意すればいいかもしれないが、それだけ秘密の漏洩になる。
そこで考え出されたのは、ネットワークによる集中管理である。ネットワークであればその制御装置本体の
設置場所をホール内である必要もなくなる。

「マルハンの店頭公開利益を見込み、第三国経由で資金調達をする。」その役目を買って出たのが先のメンバーである。
新韓銀行と新韓生命保険が伊藤忠との三角取引でマルハンへ迂回するというもの。中国も関わっているらしいが
詳細は不明なままである。金額は具体的に知らされていた。１回目が８００億円、２回目が５～６００億円というものであった。

◎ハンの今後の目標は売り上げ５兆円、500店舗、上場すること。

新スレ→○○○マルハンパチンコタワー渋谷パート１０○○○
★★★★★このスレの解説★★★★★を読んでみるとよく判る。
http://money6.2ch.net/test/read.cgi/pachij/120←くっけて→1304777/559

**名無しさん＠お腹いっぱい。** · 2008/03/04(火) 23:29:49

グラフ同形問題について次のような判定方法を考える。

あるグラフGに対し次のような数列を定義する。
ノードの集合V={v_1,v_2...v_n}とする。
ノードv_iに対し次のような数列L_iを考える。

L_i_0=1
L_i_(k+1)=L_i_k+(v_iの隣接点をv_j1,v_j2..v_jm.としてL_j1_k+L_j2_k+...L_jm_k）

また、あるkに対してL_i_k(1<=i<=n)を昇順に並べた列をS_kと置く。

二つの与えられたグラフG,G'に対し、上で定義したS_kをS_k,S'_kとおく。
あるkに対し、S_k≠S'_kとなるならGとG'は同形で無いと判定する。
任意のk(k>=0)に対しS_k=S'_kならば同形であると判定する。

このテストで同形と判定されるのに、実際は同形ではないグラフGとG'を求めよ。

**名無しさん＠お腹いっぱい。** · 2008/03/05(水) 00:02:37

あげ

**名無しさん＠お腹いっぱい。** · 2008/05/25(日) 14:23:36

3次元の宇宙地図を色塗り分けするには最低何色あればいい？

**名無しさん＠お腹いっぱい。** · 2008/06/27(金) 05:22:40

無限

**名無しさん＠お腹いっぱい。** · 2008/07/24(木) 18:14:50

グラフ理論素人なんですが、次の問題を解く一般的なアルゴリズムがあったら、
その方法か名前を教えてほしいのですが。。。

"""
無効グラフGが与えられた時に、Gを最大次数が2以下の部分グラフに分割したい。
ここで、各部分グラフはほかの部分グラフ中の頂点を含まないようにする。
このとき、最小の分割数はいくつか？
"""

要は、一筆書きに似てるんですが、与えられたグラフを最低何画で書けるか？
みたいな問題です。用語の使い方がおかしかったらすいません。