作者DJWS (...)
看板Prob_Solve
標題Re: [問題] 任給一圖如何找induced連通子圖的總數
時間Wed Feb 23 17:19:25 2011
※ 引述《ythung (費瑪連珠)》之銘言：
: 我想問的是
: 這些圖的連通子圖總數如果用excel或maple(為了科展, 我最近才開始學的)有辦法作出來嗎?
您好，
基本上您的問題現今還沒有出現漂亮的解法。
既沒有數學公式，也沒有快速的電腦計算方式（演算法）。
（就算有，那也是科學家正在研究的事情，不是我們這種普羅大眾可以理解的。:p）
要解決這個問題，最簡單的方式，
就是把全部的connected induced subgraph都列出來，
然後一個一個數。
人工去數，很慢，寫個程式讓電腦數，那就會快很多。
因為您和學生都不熟悉程式語言，而且又迫在眉睫，
所以建議您找一個懂C或C++或Java程式設計的人，
商請他幫你寫個程式，讓電腦數。
我想這裡有許多板友都有能力幫您完成程式。（但不是我 :p）
由於這個問題沒有數學公式可以套用，
所以excel和maple恐怕解決不了您的問題。
: 這看起來更有效率 (因為我覺得學生的寫法太冗長了, 作2xn矩形就花了九頁)
: 但有更多不懂的名詞
: 對我來說很難理解...
: 不知大大能不能推薦一兩本經典的演算法入門書
: 我覺得我還是得多多研究, 自我充實
演算法的書我推薦「演算法／戴顯權」這一本，
淺顯易懂，圖片也很多，很適合用來入門。
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 220.137.20.194
※ 編輯: DJWS 來自: 220.137.20.194 (02/23 17:19)
1F：推 ythung:謝謝您的推薦, 我會儘快去買來研究的 02/24 00:30
2F：推 ythung:另, 如果只討論mxn矩形, 不知有無機會用excel或maple算出 02/24 00:34
3F：推 FRAXIS:m*n的Grid Graph？ 02/24 07:42
4F：推 ythung:yes. 02/24 13:02
5F：→ DJWS:是不是等同於計算有多少個cycle？ 圍一圈這樣 02/24 13:41
6F：→ DJWS:抱歉我想錯了... 02/24 13:44
7F：推 FRAXIS:我覺得Grid Graph應該會有公式可以算.. 至少有遞迴的方法.. 02/25 08:15
8F：推 ythung:我在OEIS有看到2*n, 3*n遞迴式, 但我想知道的是程式怎麼寫 02/25 23:26
9F：推 FRAXIS:有遞迴式程式就很容易了吧.. 遞迴式是什麼？ 02/26 21:22
10F：推 ythung:2xn:a(n)=2a(n-1)+a(n-2)+4n-1, a(1)=3, a(2)=13 02/26 21:33
11F：→ ythung:3xn:a(n)=9a(n-1)-26a(n-2)+35..-22..-3..+16..-9..+a(n-8) 02/26 21:38
14F：→ FRAXIS:這個跟2*n的case很像 稍微改一下就好了 3*n的也差不多.. 02/27 04:33
15F：推 ythung:您誤會我意思了, 有遞迴式的話, 用excel很快就能找更多項 02/27 21:48
16F：→ ythung:我意指如何寫程式算出2x4的連通子圖總數是108,2x5是275,... 02/27 21:50
17F：推 ythung:我看過一個想法:在2xn格內填入0和1,找若干個1相連方法總數 02/27 21:53