問題
397 名前：１３２人目の素数さん[] 投稿日：2005/10/12(水) 22:23:00 [[アルゴリズム]]の問題なんですが。 ツリー状のグラフTが与えられたとして、 Tの部分グラフのなかで連結なものの数を求める 多項式時間アルゴリズムを示せ。
解答
400 名前：１３２人目の素数さん[sage] 投稿日：2005/10/12(水) 23:00:04 >397 同型なグラフは二重に数えてよいんだよね？ 頂点 v を含むのと含まないのとを別々に考えていけばいいんじゃない？ 含むほうは、各部分木をどこでちょん切るかを数えればいいだけだし、 含まないほうはG-vに再帰的にアルゴリズムを適用するだけ。
401 名前：１３２人目の素数さん[sage] 投稿日：2005/10/12(水) 23:01:03 ＞G-vに G-v の各連結成分に、の間違い。
402 名前：１３２人目の素数さん[sage] 投稿日：2005/10/12(水) 23:05:52 >>400 ちゃんと多項式時間で計算できるかが問題。 下手すると指数時間になる。
404 名前：１３２人目の素数さん[sage] 投稿日：2005/10/13(木) 00:16:40 >402 v に対する再帰の実行回数は、高々 n(各頂点につき一度しか実行されない)。 部分木をどこでちょんぎるか、のほうは確かに説明不足でしたね。 これも再帰的にやります。 v の部分木の一つを T' (vも含むようにとる)とします。 v の次数は 1。v の子を u として、u の各部分木(u を根とする)に対して アルゴリズムを再帰的に実行して数え、それらを掛け合わせたもの + 1 が T' のちょん切り方の個数。（+1 は v-u 間でちょん切る場合の数） 計算時間は全部でO(n^2)。 v の選び方を工夫すれば、もっと減らせそうな気はするけど、よくわからない。 ランダムな選び方は、例えばk分木の時にはあまり速くならない(ほとんど葉だから)。
405 名前：１３２人目の素数さん[sage] 投稿日：2005/10/13(木) 03:20:09 と、思ったけど、O(n) でできるのか。 最初に根となる頂点を一つ選んで、 枝を根から葉の方向に向きをつけておく。 一つ目の再帰では、常に現在見ている部分木の根を v としてとるようにすれば、 ちょん切り方を数える再帰では、各頂点ごとに一回だけ数えて覚えておけば再利用できる。 どちらの再帰も各頂点ごとに一度づつ実行されるので、トータルで O(n)。
おまけ
408 名前：397[sage] 投稿日：2005/10/13(木) 22:45:16 >>405 素晴らしいです。ところでこれが一般のグラフになると とたんに難しくなるわけですが、チャレンジしてみませんか。
409 名前：１３２人目の素数さん[] 投稿日：2005/10/13(木) 22:56:30 >>408 一般のグラフでも結論として多項式時間で計算できることはいえんの？ それとその場合のグラフは２重辺とかループとかあり？
410 名前：397[sage] 投稿日：2005/10/13(木) 23:06:06 >>409 じつは多項式時間で計算できるかどうかも私にはわかっていません。 正直私は挫折しました。 2重辺やループは無しということで。
411 名前：１３２人目の素数さん[] 投稿日：2005/10/13(木) 23:15:03 >>410 じゃあ問題はこう？ －問題－ 与えられた有限集合VとVの２元集合の族Eの組G=(V,E)に対し Gの部分グラフの数をあたえる関数f(G)はGの点の数、つまり＃Vに関して多項式時間で 計算できるか？つまりあるfを計算するアルゴリズムTと多項式Pが存在して任意のGに対して (Tがf(G)を計算する時間)≦f(Gの点の数) が成り立つか？ －－ で桶？まあ計算論ホントにやってるひとがみたらつっこみどこ満載なんだろうけど。 まあ門外漢の感覚的お遊びってことで。
414 名前：１３２人目の素数さん[sage] 投稿日：2005/10/14(金) 00:57:29 >411 #P-complete なんじゃない？ 多項式で解ける気がしないなぁ。
415 名前：１３２人目の素数さん[] 投稿日：2005/10/14(金) 01:19:22 #P-completeってNP完全って香具師？そんな略しかたするん？NPのNってnumber？
417 名前：１３２人目の素数さん[sage] 投稿日：2005/10/14(金) 01:31:18 >415 NP は non-deterministically polynomial。 #P は大雑把に言うとものを数える、という問題のクラスで、 #P-complete は #P の中で完全 （その問題が多項式で解ければどの#P問題も多項式で解ける） な問題の集合。 例えば SAT の式がいくつ解を持つか？という問題は #P-complete。 #P は NP よりも難しい。 NP は、答えが一つ以上あるかどうかを問う問題のクラスであり、 #P は答えがいくつあるかを問う問題のクラスだから。
