2ちゃんねる ★スマホ版★ ■掲示板に戻る■ 全部 1- 最新50  

■ このスレッドは過去ログ倉庫に格納されています

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

1 :名無しさん@お腹いっぱい。:2006/08/19(土) 17:36:22 ID:cJAZsUNG0
面白い問題キヴォヌ

2 :名無しさん@お腹いっぱい。:2006/08/19(土) 21:11:41 ID:pOdl4AkA0
SUBGRAPH について教えてください.

3 :名無しさん@お腹いっぱい。:2006/08/20(日) 22:57:36 ID:XL7i5uxp0
>>2
部分グラフ
点集合Vと辺集合EからなるグラフG=(V,E)の
部分グラフは G=(V',E') (V'⊆V、E'⊆E)

4 :名無しさん@お腹いっぱい。:2006/08/25(金) 01:32:17 ID:iiXC8Bi40
それだけでは定義できんのでは?
E'はV'に無関係には選べんだろ


5 :名無しさん@お腹いっぱい。:2006/09/09(土) 10:00:21 ID:qpZDxb020
>>4のいいたいことが分からない

6 :名無しさん@お腹いっぱい。:2006/09/09(土) 10:25:09 ID:98TXP2RK0
e∈E' のとき e の端点は V' に入ってないといけない

7 :3:2006/09/10(日) 03:50:05 ID:Cuj2/6WA0
うん、そうだったね
>>3は無しで
正しい定義はここに書くにはスペースが足りないようだ

8 :名無しさん@お腹いっぱい。:2006/10/08(日) 06:57:26 ID:Grg9W4Ke0
微妙にスレ違いスマソ。
ランダムグラフで各ノードがリンクのあるノードとのみ情報交換できる状態で
自律分散的にクリークを構築するアルゴリズムってなんかあるかな?

9 :名無しさん@お腹いっぱい。:2006/10/08(日) 09:34:36 ID:tIBgNBUN0
簡単だ
枝はクリークじゃないか


10 :名無しさん@お腹いっぱい。:2006/10/08(日) 11:03:56 ID:Grg9W4Ke0
>>9
いや、そうなんだけど・・・
可能な限り構成ノード三個以上、むしろ構成ノードが多いクリークでって
制約では?

11 :名無しさん@お腹いっぱい。:2006/10/11(水) 18:58:58 ID:KBtMzgMk0
自分の隣人に、それぞれの隣人リストを送ってもらって、
自分でクリーク作るしかないんじゃない?


12 :名無しさん@お腹いっぱい。:2006/10/22(日) 21:37:03 ID:+TgPQHf00
boost::graph
って専門の人からみたらどうなのでしょうか?

13 :名無しさん@お腹いっぱい。:2006/10/23(月) 05:59:07 ID:EIVu4q7J0
LEDAが高いからなぁ

14 :名無しさん@お腹いっぱい。:2006/11/11(土) 22:22:17 ID:WiVe2eyl0
教えて君です。グラフ理論とベクトルとJavaをつなぐいい本があったら
教えてくださいです。

15 :名無しさん@お腹いっぱい。:2006/11/11(土) 23:06:13 ID:6inZGTh9P
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

16 :名無しさん@お腹いっぱい。:2006/11/23(木) 00:13:48 ID:YhSoQEnG0
電車で都内周りまくって
元の位置に戻ってきて到着駅数が最大になるのは、どんなルートだい?

17 :名無しさん@お腹いっぱい。:2006/11/23(木) 09:59:01 ID:MRvctCuO0
LONGEST CYCLE問題。NP完全問題

18 :名無しさん@お腹いっぱい。:2006/11/24(金) 08:38:33 ID:tM0c8+YV0
NP「完全」じゃないだろ

19 :名無しさん@お腹いっぱい。:2006/12/01(金) 01:11:33 ID:teK/FHzR0
新聞の番組表は区切りごとに、ry)…何色あれば塗れるんかね?

20 :名無しさん@お腹いっぱい。:2006/12/06(水) 23:18:07 ID:XxnKgnkq0
平面で飛び地がなければ4色だな
http://ja.wikipedia.org/wiki/%E5%9B%9B%E8%89%B2%E5%AE%9A%E7%90%86

21 :名無しさん@お腹いっぱい。:2006/12/07(木) 10:49:32 ID:mqJjraqg0
グリッドグラフでも三彩色不可能なの?

22 :名無しさん@お腹いっぱい。:2006/12/20(水) 00:44:01 ID:7US+rxzl0
    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の番組表を塗るには必ず3色必要。
なので、C-TVを塗るには4色目が必要。よって4色以上必要。 




23 :名無しさん@お腹いっぱい。:2007/01/16(火) 08:40:00 ID:ZH63dQ0Y0
区切り用に黒、塗りつぶし用に白があれば十分

24 :名無しさん@お腹いっぱい。:2007/02/28(水) 22:39:00 ID:qOsUJAFw0
交差点が存在するグラフを、交差点が存在しないように変換するアルゴリズムてありますか?

25 :名無しさん@お腹いっぱい。:2007/03/01(木) 02:29:43 ID:cyd56aww0
交差点って何?平面グラフでないってこと?

26 :名無しさん@お腹いっぱい。:2007/03/02(金) 10:23:50 ID:t1VA26je0
平面グラフの平面描画を得たいという話ならいくらでもある

27 :名無しさん@お腹いっぱい。:2007/03/06(火) 13:15:09 ID:cfMgcB3E0
隣接行列の固有値ってどんなことに使うんですか?

28 :名無しさん@お腹いっぱい。:2007/03/11(日) 15:33:31 ID:DE3dwANy0
GoogleのPageRankを算出する時とか

29 :名無しさん@お腹いっぱい。:2007/04/04(水) 06:22:57 ID:Jz7REWYH0
>>5
E'はV'の元を結んで構成されるとして、E'の元はEにもあるってことだろ?
それが部分グラフですよって。

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

30 :名無しさん@お腹いっぱい。:2007/05/19(土) 01:17:49 ID:ge/NsFFo0
誰か,Cayley Graphの詳しい定義を教えて下さい.
いくつか,本を読んだのですが,
詳しく書かれていなかったり,理解できませんでした.

31 :名無しさん@お腹いっぱい。:2007/05/27(日) 18:26:48 ID:gNvGjqO80
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の任意の極小カットセットはカットである


32 :名無しさん@お腹いっぱい。:2007/05/30(水) 23:46:46 ID:cjSZSvZ20
グラフマイニングのためのツールを教えなさい

33 :名無しさん@お腹いっぱい。:2007/06/07(木) 16:46:22 ID:/HlYG+420
グラフとは何か答えなさい

34 :名無しさん@お腹いっぱい。:2007/10/14(日) 20:49:51 ID:v/RAxoX+0
誰か深さ優先探索を用いた有向グラフの強連結成分分解を分かりやすく教えてちょんまげ

35 :名無しさん@お腹いっぱい。:2007/11/09(金) 05:09:24 ID:KaVbehtR0
クラトウスキーの定理の証明ってどのくらい難しいですか?

36 :名無しさん@お腹いっぱい。:2007/11/12(月) 17:31:12 ID:+3zfEnma0
star factor の意味を教えてください。
よろしくお願いします。

37 :名無しさん@お腹いっぱい。:2008/02/23(土) 17:33:43 ID:/smM7zTt0
初心者な質問で申し訳ないですが、グラフ理論において平均距離とは、すべての経路長を1として到達にかかった長さ、または経由したノード数の数という認識でよろしいのでしょうか?

38 :名無しさん@お腹いっぱい。:2008/02/23(土) 17:35:40 ID:/smM7zTt0
↑訂正です。
経路長の平均もしくは、経由したノード数の平均
でした

39 :◎韓:2008/02/24(日) 03:40:00 ID:wgeL6NC30
マルハン王国の闇http://jbbs.livedoor.jp/bbs/read.cgi/game/1733/1086581896/3-8

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

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

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

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

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


40 :名無しさん@お腹いっぱい。:2008/03/04(火) 23:29:49 ID:fip/Hrrp0
グラフ同形問題について次のような判定方法を考える。

あるグラフ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'を求めよ。

41 :名無しさん@お腹いっぱい。:2008/03/05(水) 00:02:37 ID:lBXy4t6f0
あげ

42 :名無しさん@お腹いっぱい。:2008/05/25(日) 14:23:36 ID:uE7tORYz0
3次元の宇宙地図を色塗り分けするには最低何色あればいい?

43 :名無しさん@お腹いっぱい。:2008/06/27(金) 05:22:40 ID:b7/6K1YY0
無限

44 :名無しさん@お腹いっぱい。:2008/07/24(木) 18:14:50 ID:hKTZ68AD0
グラフ理論素人なんですが、次の問題を解く一般的なアルゴリズムがあったら、
その方法か名前を教えてほしいのですが。。。

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

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


45 :名無しさん@お腹いっぱい。:2008/07/24(木) 18:16:42 ID:hKTZ68AD0
>>44
無効グラフ」ではなくて「無向グラフ」でした

46 :名無しさん@お腹いっぱい。:2008/07/24(木) 18:26:45 ID:I7W3K9cO0
よくわからんが、ハミルトン閉路問題を拡張したような感じか?


47 :名無しさん@お腹いっぱい。:2008/07/24(木) 18:40:42 ID:hKTZ68AD0
>>46
ハミルトン閉路を今調べましたが、たぶんそうです。
言い換えると、
"グラフGをなるべく少数のハミルトン路(閉路じゃなくてもいい)に分割したい。"
といった感じです。


48 :名無しさん@お腹いっぱい。:2008/07/24(木) 18:40:50 ID:v/qcIfE90
>>44
> ここで、各部分グラフはほかの部分グラフ中の頂点を含まないようにする。

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

49 :名無しさん@お腹いっぱい。:2008/07/24(木) 18:42:46 ID:hKTZ68AD0
>>48
あ、そうですね。ちょっと用語が悪かったかもです。
頂点が被覆できればOKです。

50 :名無しさん@お腹いっぱい。:2008/07/24(木) 18:58:47 ID:v/qcIfE90
ハミルトン路が1個で頂点被覆できるかという問題がNP困難らしいから、
最少のハミルトン路で頂点被覆するという問題もNP困難だろう。
近似解でいいのか?

51 :名無しさん@お腹いっぱい。:2008/07/24(木) 19:24:44 ID:I7W3K9cO0
なかなか面白そうな問題ではあるが、俺には貪欲サーチよりマシなアイディアが浮かばないぜ。orz
誤差に保障のある近似解すら難しそうな予感。



52 :名無しさん@お腹いっぱい。:2008/07/24(木) 20:05:14 ID:hKTZ68AD0
>>50
自分が今解きたい問題では、頂点数がせいぜい20個くらいで、
近似ではなくて厳密解がほしいといった状況です。


53 :名無しさん@お腹いっぱい。:2008/07/24(木) 20:15:09 ID:I7W3K9cO0
頂点数20か。
辺の数も大事なんだけど、辺の数はいくつぐらい?



54 :名無しさん@お腹いっぱい。:2008/07/24(木) 20:34:26 ID:hKTZ68AD0
>>53
頂点数nは最大で20くらいかなって感じで、大体10前後くらいで収まりそうです。
辺数は n * n / 2 前後といったところです。

55 :名無しさん@お腹いっぱい。:2008/07/24(木) 20:38:18 ID:hKTZ68AD0
>>54
すいません、もうちょっと少なくて、辺数 n * n / 3くらいでした。

56 :名無しさん@お腹いっぱい。:2008/07/24(木) 21:09:34 ID:I7W3K9cO0
本当に厳密解ということになると、全探索に近いことが必要になってくるだろうね。
俺にはバックトラック法とかぐらいしか思いつかんなぁ。
上手く枝刈りが決まればぎりぎりいけそうなサイズではある。
この程度のことしかいえなくてすんません。


57 :名無しさん@お腹いっぱい。:2008/07/24(木) 23:30:16 ID:AbtatZee0
質問させてください。
2部グラフには最大マッチング最小被覆定理が成立するということは分かったのですが、
実際にどのvertexを選べば最小被覆なのかを知ろうと思えば、どういう方法をとればいいのでしょうか?

58 :名無しさん@お腹いっぱい。:2008/07/24(木) 23:37:56 ID:rhLCiqmK0
俺にも、しらみつぶししか思いつかない。

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


59 :名無しさん@お腹いっぱい。:2008/09/24(水) 01:06:58 ID:dq6jgnmg0
>44
もう遅いと思うけど、
線形計画法を使えば簡単にとけます。

変数 e_i を

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

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

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

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

Σ e_i (Σは全ての枝での和)

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

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

60 :名無しさん@お腹いっぱい。:2008/09/24(水) 01:25:10 ID:dq6jgnmg0
もっとアルゴリズムっぽいやり方でやるなら、
適当な解から初めて
* 増大パスを見つける
* 見つけたパス上の枝の選択状況を入れ替える
(選択されていなかった枝は未選択に、未選択の枝は選択)
という操作を繰り返すことで見つかるんじゃないかな?
(二部グラフの最大マッチングと似たアルゴリズムということです。)

61 :名無しさん@お腹いっぱい。:2008/09/24(水) 12:29:05 ID:uhVZYgcA0
ILPになるから多項式時間にならないのでは?

62 :名無しさん@お腹いっぱい。:2008/09/24(水) 13:27:35 ID:dq6jgnmg0
あぁ、本当だ。失礼しました。

63 :名無しさん@お腹いっぱい。:2008/10/24(金) 02:07:37 ID:rWAuE4pX0
板の内容とは違うんだがグラフアルゴリズムでいい先生いないか?
大学院入ってやりたいと思ってるんだが。
日本じゃなくてもいい。

64 :名無しさん@お腹いっぱい。:2008/10/31(金) 21:05:25 ID:r/PvJAY+0
誰か俺の卒研のプログラミング手伝ってくれない?
最低でも10万は払う。

65 :名無しさん@お腹いっぱい。:2008/10/31(金) 21:20:43 ID:VsBwgHwk0
まずはテーマを晒してもらおうか。
テーマが面白ければ食いつく奴もいるかも知れんし。
10万で>>64の専属プログラマーになって卒研完成まで面倒見てくれる奇特なやつは多分いないだろうが、
ヒントやアドバイスくらいなら得られるだろ。



66 :名無しさん@お腹いっぱい。:2008/11/01(土) 10:56:38 ID:8vgsYBL20
週10万とか?

67 :名無しさん@お腹いっぱい。:2008/11/01(土) 20:58:44 ID:KYjWl1oc0
プロのプログラマを一人、フルタイムで雇ったら週20万てとこかな。


68 :名無しさん@お腹いっぱい。:2008/11/06(木) 22:57:13 ID:XI6AtgLJ0
vc

69 :名無しさん@お腹いっぱい。:2008/11/08(土) 21:00:58 ID:RMt6IAeJ0
>>67

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

70 :名無しさん@お腹いっぱい。:2008/11/14(金) 19:20:54 ID:u/rbiZmc0
1:あるグラフGはk個の連結成分からなり、各成分は木。
Gの頂点の個数をnとするとき、Fの辺の個数はいくつか

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

71 :名無しさん@お腹いっぱい。:2008/12/03(水) 17:04:21 ID:3eSyYLR90
無向グラフが隣接リストで表されているとき、このグラフがサイクルを含むかどうかを判断するアルゴリズム、それもO(V)って一体どんなものですか?

72 :名無しさん@お腹いっぱい。:2008/12/03(水) 18:18:53 ID:rwcucmdt0
グラフが連結なら、各頂点が次数を保持してるという前提で、次数を足すだけだがな。

73 :名無しさん@お腹いっぱい。:2008/12/04(木) 06:41:39 ID:quCVWM3L0
おーありがとう。

74 :名無しさん@お腹いっぱい。:2009/04/20(月) 20:50:50 ID:w2nPV0s00
最大流問題を解いて最小カットを見つけたいけど、
最近ではどのアルゴリズムがいいとされているの?

75 :名無しさん@お腹いっぱい。:2010/02/20(土) 01:22:14 ID:3TqoBHVs0
そういやファルカーソンの定理とかあったなあ。

18 KB
■ このスレッドは過去ログ倉庫に格納されています

★スマホ版★ 掲示板に戻る 全部 前100 次100 最新50

read.cgi ver 05.02.02 2014/06/23 Mango Mangüé ★
FOX ★ DSO(Dynamic Shared Object)