作者ythung (费玛连珠)
看板Math
标题[图论] 如何找一个图的所有连通子图的个数
时间Sun Feb 20 13:18:59 2011
任给一图
如何找其所有连通子图的个数
一些特定图还可以用排列组合算
但若特殊图呢
例：
．．．
． ．
．．． (8个顶点，写成"曰"字)
．．．
．．．
．．． (9个顶点，写成"口"+"米")
．．．
．．．
．．． (9个顶点，写成"田"+转45度的"口")
不知那一本图论(或离散数学)的书里有找连通子图的演算法(或程式)？
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 124.9.128.172
※ 编辑: ythung 来自: 124.9.128.172 (02/20 13:21)
1F：推 hcsoso :跑 BFS 应该就可以了? 是 undirected graphs 吗? 02/20 14:44
2F：→ hcsoso :噢抱歉, 是连通"子图"... 02/20 14:44
3F：推 hcsoso :你的连通子图需要 spanning 吗? 如果是的话, 这个问 02/20 14:59
4F：→ hcsoso :题等价於计算图的 Tutte polynomial 在 (1,2) 的值, 02/20 15:00
5F：→ hcsoso :in general 应该是个很难的问题... 也许算小的图可以 02/20 15:00
6F：→ hcsoso :暴力的解出 Tutte polynomial. 02/20 15:01
9F：→ DJWS :组合数学的书可能有资料 02/20 15:04
10F：推 hcsoso :那个连结似乎只有给出估计? 02/20 15:10
11F：推 DJWS :啊 那真不好意思 当作我没推文吧... 02/20 15:17
12F：推 hcsoso :DP 应该可以给出 exponential time 解. 02/20 15:18
13F：→ hcsoso :That's ok! 说不定原 po 是要近似解 XD 02/20 15:19
14F：→ ythung :是undirected graphs.不知子图的spanning是什麽? 02/20 16:11
15F：→ ythung :我的连通子图是指原图去掉某些点(及其附着边)仍连通 02/20 16:12
16F：→ ythung :另我这些例子是作科展衍生的图,点数都不多(<20点) 02/20 16:18
17F：→ ythung :如果要暴力解法, 程式演算法该如何写? 另请教DP是? 02/20 16:20
18F：→ ythung :另我需要的是准确值, 非近似解 02/20 16:21
19F：→ ythung :刚查wiki, 我的子图不是spanning , 而是induced 02/20 16:34
20F：→ THEJOY :dynamaic programing? 02/20 19:17
21F：→ suhorng :喔,20个点超小的XD 很适合DP的范围 02/20 19:29
22F：→ suhorng :状态大概是 dp[1<<20], 对每个点纪录有/没有 02/20 19:30
23F：→ suhorng :在你的子图中,所以有 2^N 种状态. 每种状态就记方法 02/20 19:30
24F：推 hcsoso :现在看来真的得用 DP 解. induced connected 子图的 02/21 09:42
25F：→ hcsoso :计算是 #P-hard, 一般不认为有多项式时间演算法. 02/21 09:42
26F：→ ythung :DP是THETOY大大说的dynamaic programming吗? 02/21 11:34
27F：→ ythung :有演算法可供参考吗？我们学生作2xn矩形,但用座标 02/21 11:44
28F：→ ythung :写了九页A4的程式码, 我想应该有更简的演算法才对 02/21 11:45
29F：→ ythung :有办法用excel或maple写吗？(我是念纯数的,电脑很弱) 02/21 11:47
30F：推 hcsoso :是的, 就是 dynamic programming. 到计算数学版问 02/21 16:26
31F：→ hcsoso :我想会有程式的强者提供说明! (Prob_Solve 板) 02/21 16:26