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

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

面白い問題ｷｳﾞｫﾇ

**名無しさん＠お腹いっぱい。** · 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

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