Re: [問題] 任給一圖如何找induced連通子圖的總數

[DJWS (...)]

※ 引述《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)
推 ythung:謝謝您的推薦, 我會儘快去買來研究的
推 ythung:另, 如果只討論mxn矩形, 不知有無機會用excel或maple算出
推 FRAXIS:m*n的Grid Graph？
推 ythung:yes.
→ DJWS:是不是等同於計算有多少個cycle？　圍一圈這樣
→ DJWS:抱歉我想錯了...
推 FRAXIS:我覺得Grid Graph應該會有公式可以算.. 至少有遞迴的方法..
推 ythung:我在OEIS有看到2*n, 3*n遞迴式, 但我想知道的是程式怎麼寫
推 FRAXIS:有遞迴式程式就很容易了吧.. 遞迴式是什麼？
推 ythung:2xn:a(n)=2a(n-1)+a(n-2)+4n-1, a(1)=3, a(2)=13
→ ythung:3xn:a(n)=9a(n-1)-26a(n-2)+35..-22..-3..+16..-9..+a(n-8)
→ ythung:網址：http://oeis.org/A059021
→ FRAXIS:http://en.wikibooks.org/wiki/Fibonacci_number_program
→ FRAXIS:這個跟2*n的case很像 稍微改一下就好了 3*n的也差不多..
推 ythung:您誤會我意思了, 有遞迴式的話, 用excel很快就能找更多項
→ ythung:我意指如何寫程式算出2x4的連通子圖總數是108,2x5是275,...
推 ythung:我看過一個想法:在2xn格內填入0和1,找若干個1相連方法總數