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

面白い問題ｷｳﾞｫﾇ

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

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

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

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

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

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

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

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

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

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

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

LEDAが高いからなぁ

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

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

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

LONGEST CYCLE問題。NP完全問題

NP「完全」じゃないだろ

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

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

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

　　　　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を塗るには４色目が必要。よって４色以上必要。　

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

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

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

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

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

GoogleのPageRankを算出する時とか

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

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

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

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の任意の極小カットセットはカットである

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

あげ

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

無限

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

変数 e_i を

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

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

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

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

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

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

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

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

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

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

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

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

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

週10万とか？

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

vc

>>67

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

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

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

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

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

おーありがとう。

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

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

いわゆる地図の四色問題じゃなくて、三次元だと何色が最小かな？
色で「充填」も可能ってことで。

たとえば正四面体を塗り分けるには四色必要。この塗り分けられた正四面体の中身にも色を「充填」するとなると五色目が必要。
でもって、更に、もしも中身に四面全てに接するチューブがあったら六色目もいる？

n次だとどうなるんだろうか？

そんなチューブを互いに接するように増やしていけばいくらでも色が必要になるなって考えてたら、Wikipedia:四色定理に書いてあったorz