PTT數位生活區 / Prob_Solve (計算數學 Problem Solving)

Re: [問題] 任給一圖如何找induced連通子圖的總數

看板Prob_Solve (計算數學 Problem Solving)作者ythung (費瑪連珠)時間13年前 (2011/02/23 00:17)推噓0(0推 0噓 3→)

留言3則, 2人參與討論串3/4 (看更多)

※ 引述《tkcn (小安)》之銘言： : ※ 引述《ythung (費瑪連珠)》之銘言： : : 本來在Math板問 : : 有高人指點可以來這裡請教(汗~~今天才知道ptt有這個板) : : 任給一圖(simple undirected graph) : : 如何找其所有induced連通子圖的總個數 : : 一些特定圖還可以用排列組合算 : : 但若特殊圖呢(目前我討論的圖頂點數最多20點) : 跑去 math 板看了原文，那幾位推文的強者根本就都會嘛 XD : 因為最多也才 20 個點，所以可能的解最多也只有 2^20 (約 10^6) : 就算每個解都跑一次 DFS/BFS，一組 Graph 我估計幾分鐘之內多半也能算完吧。真是隔行如隔山(我以前是念純數的) DFS? BFS? 都不知是啥剛去google一下 http://www.csie.ntnu.edu.tw/~u91029/GraphTraversal.html 才知道是"圖論中兩種遍歷演算法Depth-first Search和Breadth-first Search" 其實我在computer方面根本沒啥基礎只有在大學(20年前的事了)修過資訊概論, 離散數學, 數值分析之類的課程當時也學過BASIC,Pascal及C語言(但也差不多忘光了) 畢竟年代久遠了所以現在要重拾書本備感吃力(恐怕也有點緩不濟急) 但科展作品的修改(學生已通過校內初審)迫在眉睫所以只好上網求教眾高手我想問的是這些圖的連通子圖總數如果用excel或maple(為了科展, 我最近才開始學的)有辦法作出來嗎? 如果以我原文任一個圖作一具體程式的實例我可能就會更快速理解了當然用我曾學過的語言也可以(只是我已不知道去那裡找那些語言的程式) : 如果要有效率一點的方式，可以從一個 node 開始(此時必為 connected)， : 用 BFS 每次把現有的解加入一個 neighbor，形成一個新的解。 : 因為加的都是 neighbor，所以必定 connected。 : 如果新的解先前已經產生過就略過不計， : BFS 總共經過幾回合就會是答案了。 : (突然覺得這解法跟上面有篇樂透的根本一樣嘛) : 繼續加速的技巧也跟樂透一樣，善用 bitwise operations。 : 每一組解都對應成 bits pattern， : adjacency matrix 也用 bits 來表示， : 這樣在加入新 neighbor 的地方， : 就可以用 bitwise operations 達成。 : 舉例來說目前的解為 {3}，state 就會是 00000100 : {3} 有兩個 neighbors: {1},{5}，adj 為 00010001 : 第一步先加入 {1}，新的 state 成為 00000101， : 假設 {1} 的 neighbors 為 {2},{3},{6}，adj 即為 00100110。 : 那麼 {1,3} 的 neighbors 就可以直接算出: : 00010001 | 00100110 & (~00000101) = 00100010 : ^ ^ ^ ^ : | | | 新的 state 的 neighbors : | | 新的 state : | 新加入 vertex 的 neighbors : 原state 的 neighbors 這看起來更有效率 (因為我覺得學生的寫法太冗長了, 作2xn矩形就花了九頁) 但有更多不懂的名詞對我來說很難理解... 不知大大能不能推薦一兩本經典的演算法入門書我覺得我還是得多多研究, 自我充實 ※ 編輯: ythung 來自: 124.9.130.97 (02/23 00:20)