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

**名無しさん＠お腹いっぱい。** · 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以下の部分グラフに分割したい。
ここで、各部分グラフはほかの部分グラフ中の頂点を含まないようにする。
このとき、最小の分割数はいくつか？
"""

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

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

>>44
無効グラフ」ではなくて「無向グラフ」でした

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

よくわからんが、ハミルトン閉路問題を拡張したような感じか？

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

>>46
ハミルトン閉路を今調べましたが、たぶんそうです。
言い換えると、
"グラフGをなるべく少数のハミルトン路(閉路じゃなくてもいい)に分割したい。"
といった感じです。

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

>>44
> ここで、各部分グラフはほかの部分グラフ中の頂点を含まないようにする。

それだと、Gの枝全部を被覆できないんじゃないか？
頂点が被覆できればいいのか？

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

>>48
あ、そうですね。ちょっと用語が悪かったかもです。
頂点が被覆できればOKです。

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

ハミルトン路が1個で頂点被覆できるかという問題がNP困難らしいから、
最少のハミルトン路で頂点被覆するという問題もNP困難だろう。
近似解でいいのか？

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

なかなか面白そうな問題ではあるが、俺には貪欲サーチよりマシなアイディアが浮かばないぜ。orz
誤差に保障のある近似解すら難しそうな予感。

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

>>50
自分が今解きたい問題では、頂点数がせいぜい20個くらいで、
近似ではなくて厳密解がほしいといった状況です。

**名無しさん＠お腹いっぱい。** · 2008/07/24(木) 20:15:09

頂点数２０か。
辺の数も大事なんだけど、辺の数はいくつぐらい？

**名無しさん＠お腹いっぱい。** · 2008/07/24(木) 20:34:26

>>53
頂点数nは最大で20くらいかなって感じで、大体10前後くらいで収まりそうです。
辺数は n * n / 2 前後といったところです。

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

>>54
すいません、もうちょっと少なくて、辺数 n * n / 3くらいでした。

**名無しさん＠お腹いっぱい。** · 2008/07/24(木) 21:09:34

本当に厳密解ということになると、全探索に近いことが必要になってくるだろうね。
俺にはバックトラック法とかぐらいしか思いつかんなぁ。
上手く枝刈りが決まればぎりぎりいけそうなサイズではある。
この程度のことしかいえなくてすんません。

**名無しさん＠お腹いっぱい。** · 2008/07/24(木) 23:30:16

質問させてください。
2部グラフには最大マッチング最小被覆定理が成立するということは分かったのですが、
実際にどのvertexを選べば最小被覆なのかを知ろうと思えば、どういう方法をとればいいのでしょうか？

**名無しさん＠お腹いっぱい。** · 2008/07/24(木) 23:37:56

俺にも、しらみつぶししか思いつかない。

・長さ0の単純路をすべて列挙する。
・k=0からn（頂点数）-1まで順に増やす:
　・長さkの単純路がすべてわかってるとして、長さk+1の単純路を列挙する。
・長さ0からnまでのすべての単純路を、それが通過する頂点の集合で識別する。
　（頂点数のビット数のビットパターンで表現する）
　重複がありうるけど重複する単純路は一つにまとめても問題ないはず。
・k=1からn（頂点数）まで順に増やす:
　・k個の単純路のすべての組合せを作って、
　　その中の任意の2個のビットパターンの積が0で、
　　k個のビットパターンの和が1111...1のものがあれば、それが求める分割。

**名無しさん＠お腹いっぱい。** · 2008/09/24(水) 01:06:58

>44
もう遅いと思うけど、
線形計画法を使えば簡単にとけます。

変数 e_i を

e_i = { グラフの分割後、枝 i が残っているなら 1, 残って無いなら 0 }

という意味を持つものとする。

このとき、問題を解くためには、

∀v 　Σe_i <= 2 (Σは頂点 v につながる枝に関する和)
という条件を満たしながら、

Σ e_i （Σは全ての枝での和）

を最大化するような e_i を見つければよい。
これは LP を使うと多項式時間で解ける。

画数を最小にすることがなぜΣe_i を最大化することと
同値なのかは考えてみてください。

**名無しさん＠お腹いっぱい。** · 2008/09/24(水) 01:25:10

もっとアルゴリズムっぽいやり方でやるなら、
適当な解から初めて
* 増大パスを見つける
* 見つけたパス上の枝の選択状況を入れ替える
(選択されていなかった枝は未選択に、未選択の枝は選択）
という操作を繰り返すことで見つかるんじゃないかな？
（二部グラフの最大マッチングと似たアルゴリズムということです。）

**名無しさん＠お腹いっぱい。** · 2008/09/24(水) 12:29:05

ILPになるから多項式時間にならないのでは？

**名無しさん＠お腹いっぱい。** · 2008/09/24(水) 13:27:35

あぁ、本当だ。失礼しました。

**名無しさん＠お腹いっぱい。** · 2008/10/24(金) 02:07:37

板の内容とは違うんだがグラフアルゴリズムでいい先生いないか？
大学院入ってやりたいと思ってるんだが。
日本じゃなくてもいい。

**名無しさん＠お腹いっぱい。** · 2008/10/31(金) 21:05:25

誰か俺の卒研のプログラミング手伝ってくれない？
最低でも10万は払う。

**名無しさん＠お腹いっぱい。** · 2008/10/31(金) 21:20:43

まずはテーマを晒してもらおうか。
テーマが面白ければ食いつく奴もいるかも知れんし。
１０万で>>64の専属プログラマーになって卒研完成まで面倒見てくれる奇特なやつは多分いないだろうが、
ヒントやアドバイスくらいなら得られるだろ。

**名無しさん＠お腹いっぱい。** · 2008/11/01(土) 10:56:38

週10万とか？

**名無しさん＠お腹いっぱい。** · 2008/11/01(土) 20:58:44

プロのプログラマを一人、フルタイムで雇ったら週20万てとこかな。

**名無しさん＠お腹いっぱい。** · 2008/11/06(木) 22:57:13

**名無しさん＠お腹いっぱい。** · 2008/11/08(土) 21:00:58

>>67

どの程度を指しているか知らないけれど、
安すぎるよ。

**名無しさん＠お腹いっぱい。** · 2008/11/14(金) 19:20:54

１：あるグラフGはｋ個の連結成分からなり、各成分は木。
Gの頂点の個数をｎとするとき、Fの辺の個数はいくつか

２：連結な平面グラフGにおいて、頂点の個数をｎ、辺の個数をｍ
Gは閉路を含むが辺を１つずつ除去することで閉路を含まない連結グラフを作る
最低いくつの辺を除去すればよいか
宿題なんだけど教えてくれ

**名無しさん＠お腹いっぱい。** · 2008/12/03(水) 17:04:21

無向グラフが隣接リストで表されているとき、このグラフがサイクルを含むかどうかを判断するアルゴリズム、それもO(V)って一体どんなものですか？

**名無しさん＠お腹いっぱい。** · 2008/12/03(水) 18:18:53

グラフが連結なら、各頂点が次数を保持してるという前提で、次数を足すだけだがな。

**名無しさん＠お腹いっぱい。** · 2008/12/04(木) 06:41:39

おーありがとう。

**名無しさん＠お腹いっぱい。** · 2009/04/20(月) 20:50:50

最大流問題を解いて最小カットを見つけたいけど、
最近ではどのアルゴリズムがいいとされているの？

**名無しさん＠お腹いっぱい。** · 2010/02/20(土) 01:22:14

そういやファルカーソンの定理とかあったなあ。