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