看板 [ Prob_Solve ]
討論串[問題] 任給一圖如何找induced連通子圖的總數
共 4 篇文章
內容預覽： 開啟 | 關閉 | 只限未讀
首頁
上一頁
1
下一頁
尾頁
#1
[問題] 任給一圖如何找induced連通子圖的總數
推噓0(0推 0噓 0→)留言0則，0人參與, 最新作者ythung (費瑪連珠)時間13年前 (2011/02/21 21:29), 編輯資訊
1
0
0
內容預覽:
本來在Math板問. 有高人指點可以來這裡請教(汗~~今天才知道ptt有這個板). 任給一圖(simple undirected graph). 如何找其所有induced連通子圖的總個數. 一些特定圖還可以用排列組合算. 但若特殊圖呢(目前我討論的圖頂點數最多20點). 例：. ．．．. ． ．.
(還有47個字)
#2
Re: [問題] 任給一圖如何找induced連通子圖的總數
推噓0(0推 0噓 0→)留言0則，0人參與, 最新作者tkcn (小安)時間13年前 (2011/02/22 10:42), 編輯資訊
0
0
0
內容預覽:
跑去 math 板看了原文，那幾位推文的強者根本就都會嘛 XD. 因為最多也才 20 個點，所以可能的解最多也只有 2^20 (約 10^6). 就算每個解都跑一次 DFS/BFS，一組 Graph 我估計幾分鐘之內多半也能算完吧。. 如果要有效率一點的方式，可以從一個 node 開始(此時必為 c
(還有1061個字)
#3
Re: [問題] 任給一圖如何找induced連通子圖的總數
推噓0(0推 0噓 3→)留言3則，0人參與, 最新作者ythung (費瑪連珠)時間13年前 (2011/02/23 00:17), 編輯資訊
1
0
1
內容預覽:
真是隔行如隔山(我以前是念純數的). DFS? BFS? 都不知是啥. 剛去google一下. http://www.csie.ntnu.edu.tw/~u91029/GraphTraversal.html. 才知道是"圖論中兩種遍歷演算法Depth-first Search和Breadth-fir
(還有312個字)
#4
Re: [問題] 任給一圖如何找induced連通子圖的總數
推噓10(10推 0噓 7→)留言17則，0人參與, 最新作者DJWS (...)時間13年前 (2011/02/23 17:19), 編輯資訊
0
0
0
內容預覽:
您好，. 基本上您的問題現今還沒有出現漂亮的解法。. 既沒有數學公式，也沒有快速的電腦計算方式（演算法）。. （就算有，那也是科學家正在研究的事情，不是我們這種普羅大眾可以理解的。:p）. 要解決這個問題，最簡單的方式，. 就是把全部的connected induced subgraph都列出來，.
(還有186個字)
首頁
上一頁
1
下一頁
尾頁