作者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