[圖論] 如何找一個圖的所有連通子圖的個數

[ythung (費瑪連珠)]

任給一圖
如何找其所有連通子圖的個數

一些特定圖還可以用排列組合算
但若特殊圖呢

例：

．．．
．　．
．．．　(8個頂點，寫成"曰"字)


．．．
．．．
．．．  (9個頂點，寫成"口"+"米")

．．．
．．．
．．．　(9個頂點，寫成"田"+轉45度的"口")

不知那一本圖論(或離散數學)的書裡有找連通子圖的演算法(或程式)？

--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 124.9.128.172
※ 編輯: ythung          來自: 124.9.128.172        (02/20 13:21)
推 hcsoso      :跑 BFS 應該就可以了? 是 undirected graphs 嗎?
→ hcsoso      :噢抱歉, 是連通"子圖"...
推 hcsoso      :你的連通子圖需要 spanning 嗎? 如果是的話, 這個問
→ hcsoso      :題等價於計算圖的 Tutte polynomial 在 (1,2) 的值,
→ hcsoso      :in general 應該是個很難的問題... 也許算小的圖可以
→ hcsoso      :暴力的解出 Tutte polynomial.
→ hcsoso      :http://en.wikipedia.org/wiki/Tutte_polynomial
推 DJWS        :http://ppt.cc/B6ex  第24頁  是這個嗎？
→ DJWS        :組合數學的書可能有資料
推 hcsoso      :那個連結似乎只有給出估計?
推 DJWS        :啊  那真不好意思  當作我沒推文吧...
推 hcsoso      :DP 應該可以給出 exponential time 解.
→ hcsoso      :That's ok! 說不定原 po 是要近似解 XD
→ ythung      :是undirected graphs.不知子圖的spanning是什麼?
→ ythung      :我的連通子圖是指原圖去掉某些點(及其附著邊)仍連通
→ ythung      :另我這些例子是作科展衍生的圖,點數都不多(<20點)
→ ythung      :如果要暴力解法, 程式演算法該如何寫? 另請教DP是?
→ ythung      :另我需要的是準確值, 非近似解
→ ythung      :剛查wiki, 我的子圖不是spanning , 而是induced
→ THEJOY      :dynamaic programing?
→ suhorng     :喔,20個點超小的XD 很適合DP的範圍
→ suhorng     :狀態大概是 dp[1<<20], 對每個點紀錄有/沒有
→ suhorng     :在你的子圖中,所以有 2^N 種狀態. 每種狀態就記方法
推 hcsoso      :現在看來真的得用 DP 解. induced connected 子圖的
→ hcsoso      :計算是 #P-hard, 一般不認為有多項式時間演算法.
→ ythung      :DP是THETOY大大說的dynamaic programming嗎?
→ ythung      :有演算法可供參考嗎？我們學生作2xn矩形,但用座標
→ ythung      :寫了九頁A4的程式碼, 我想應該有更簡的演算法才對
→ ythung      :有辦法用excel或maple寫嗎？(我是念純數的,電腦很弱)
推 hcsoso      :是的, 就是 dynamic programming. 到計算數學版問
→ hcsoso      :我想會有程式的強者提供說明! (Prob_Solve 板)