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

看板Math作者 (費瑪連珠)時間15年前 (2011/02/20 13:19), 編輯推噓8(8推 0噓 23→)
留言31則, 5人參與, 最新討論串1/1
任給一圖 如何找其所有連通子圖的個數 一些特定圖還可以用排列組合算 但若特殊圖呢 例： ．．． ．　． ．．．　(8個頂點，寫成"曰"字) ．．． ．．． ．．． (9個頂點，寫成"口"+"米") ．．． ．．． ．．．　(9個頂點，寫成"田"+轉45度的"口") 不知那一本圖論(或離散數學)的書裡有找連通子圖的演算法(或程式)？ -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 124.9.128.172 ※ 編輯: ythung 來自: 124.9.128.172 (02/20 13:21)
推
02/20 14:44, , 1F
跑 BFS 應該就可以了? 是 undirected graphs 嗎?
02/20 14:44, 1F
→
02/20 14:44, , 2F
噢抱歉, 是連通"子圖"...
02/20 14:44, 2F
推
02/20 14:59, , 3F
你的連通子圖需要 spanning 嗎? 如果是的話, 這個問
02/20 14:59, 3F
→
02/20 15:00, , 4F
題等價於計算圖的 Tutte polynomial 在 (1,2) 的值,
02/20 15:00, 4F
→
02/20 15:00, , 5F
in general 應該是個很難的問題... 也許算小的圖可以
02/20 15:00, 5F
→
02/20 15:01, , 6F
暴力的解出 Tutte polynomial.
02/20 15:01, 6F
→
02/20 15:01, , 7F
02/20 15:01, 7F
推
02/20 15:03, , 8F
http://ppt.cc/B6ex 第24頁 是這個嗎？
02/20 15:03, 8F
→
02/20 15:04, , 9F
組合數學的書可能有資料
02/20 15:04, 9F
推
02/20 15:10, , 10F
那個連結似乎只有給出估計?
02/20 15:10, 10F
推
02/20 15:17, , 11F
啊 那真不好意思 當作我沒推文吧...
02/20 15:17, 11F
推
02/20 15:18, , 12F
DP 應該可以給出 exponential time 解.
02/20 15:18, 12F
→
02/20 15:19, , 13F
That's ok! 說不定原 po 是要近似解 XD
02/20 15:19, 13F
→
02/20 16:11, , 14F
是undirected graphs.不知子圖的spanning是什麼?
02/20 16:11, 14F
→
02/20 16:12, , 15F
我的連通子圖是指原圖去掉某些點(及其附著邊)仍連通
02/20 16:12, 15F
→
02/20 16:18, , 16F
另我這些例子是作科展衍生的圖,點數都不多(<20點)
02/20 16:18, 16F
→
02/20 16:20, , 17F
如果要暴力解法, 程式演算法該如何寫? 另請教DP是?
02/20 16:20, 17F
→
02/20 16:21, , 18F
另我需要的是準確值, 非近似解
02/20 16:21, 18F
→
02/20 16:34, , 19F
剛查wiki, 我的子圖不是spanning , 而是induced
02/20 16:34, 19F
→
02/20 19:17, , 20F
dynamaic programing?
02/20 19:17, 20F
→
02/20 19:29, , 21F
喔,20個點超小的XD 很適合DP的範圍
02/20 19:29, 21F
→
02/20 19:30, , 22F
狀態大概是 dp[1<<20], 對每個點紀錄有/沒有
02/20 19:30, 22F
→
02/20 19:30, , 23F
在你的子圖中,所以有 2^N 種狀態. 每種狀態就記方法
02/20 19:30, 23F
推
02/21 09:42, , 24F
現在看來真的得用 DP 解. induced connected 子圖的
02/21 09:42, 24F
→
02/21 09:42, , 25F
計算是 #P-hard, 一般不認為有多項式時間演算法.
02/21 09:42, 25F
→
02/21 11:34, , 26F
DP是THETOY大大說的dynamaic programming嗎?
02/21 11:34, 26F
→
02/21 11:44, , 27F
有演算法可供參考嗎？我們學生作2xn矩形,但用座標
02/21 11:44, 27F
→
02/21 11:45, , 28F
寫了九頁A4的程式碼, 我想應該有更簡的演算法才對
02/21 11:45, 28F
→
02/21 11:47, , 29F
有辦法用excel或maple寫嗎？(我是念純數的,電腦很弱)
02/21 11:47, 29F
推
02/21 16:26, , 30F
是的, 就是 dynamic programming. 到計算數學版問
02/21 16:26, 30F
→
02/21 16:26, , 31F
我想會有程式的強者提供說明! (Prob_Solve 板)
02/21 16:26, 31F
‣ 更多 ythung 的文章
文章代碼(AID): #1DOAH8F1 (Math)