作者ythung (费玛连珠)
看板Prob_Solve
标题[问题] 任给一图如何找induced连通子图的总数
时间Mon Feb 21 21:29:34 2011
本来在Math板问
有高人指点可以来这里请教(汗~~今天才知道ptt有这个板)
任给一图(simple undirected graph)
如何找其所有induced连通子图的总个数
一些特定图还可以用排列组合算
但若特殊图呢(目前我讨论的图顶点数最多20点)
例：
．．．
． ．
．．． (8个顶点，写成"曰"字)
．．．
．．．
．．． (9个顶点，写成"口"+"米")
(这个我用排列组合算：2^8+8*7+1=313种)
．．．
．．．
．．． (9个顶点，写成"田"+转45度的"口")
徵求找上列任一例子的induced连通子图的演算法(或程式)？
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 124.9.128.195