1. 這題要找最小直徑樹
不知道是不是可以用All pair shortest path建立一個table, 然後總和每一列取最小值, 則該列為樹的MDST? 時間複雜度n^3?
然後我發現網路上 http://www.csie.ntnu.edu.tw/~u91029/SpanningTree.html 裡面介紹的M.D.S.T. 想法好像跟我一樣, 可是它標示是錯誤的..請問為什麼呢?
2. 這題說要用switch連結multistage network的各個process(圖片不太清楚..另外畫了一張在下面), 請問可以用complete graph來表示嗎? 也就是各個點代表各個process, 而各邊代表switch這樣作嗎?(因為它沒說可以藉由中繼的處理器來連結, 所以考慮成每個處理器都要有獨立的開關), 不知道這樣對不對?
謝謝
2 則留言:
1. 你參考的那一篇錯誤在於因為 shortest path tree 不唯一, 所以除非去窮舉出所有的shortest path trees, 否則即使是對 G=(V,E) 中的每一點都去找出他們的一個shortest path tree, 也不見得會MDST會包含於這些shortest path tree
譬如說考慮 G 為一個含有6個點的graph長得像這樣: "日", 假設編號由上至下由左至右依序是 a,b,c,d,e,f, 那麼我們對 c 所找出來的SPT T' 可以是 T'=(V,E'), 其中 E'={(a,c),(c,d),(b,d),(c,e),(e,f)}, 同理對 d 點可以找到一個同構於 T' 的SPT; 另外, 對 a 點我們可以找到SPT T'' 長得像:"Ｅ", 同理b,e,f 這3個點我們一樣可以對他們分別找出一個同構於 T'' 的SPT; 然而 T' 和 T'' 皆不為MDST, 因為我們可以找出一個 ST T*長得像: "Ｈ", 那麼顯然的, dia(T') = dia(T'') = 4 > dia(T*) = 3
你的方法的直覺方向很不錯, 但如何在算出diameter之後把MDST建出來也是一個問題, 得再仔細想想; 有一個較基本建 MDST 的方法可在 O(|E||V|log|V|) 時間內完成, 該方法也是以計算all-pair shortest path做為出發點, 但細節以及正確性的部分因為有一點複雜所以我就先不提了, 若你有興趣你可再去找MDST相關的paper來讀一讀
2. 這題比較是像是network topology的東西, 和離散裡圖論所提的東西其實不太一樣, 你可能要去翻翻computer architecture的相關書籍, 查一下那兩種topologies的定義再來做會比較好
謝謝助教:)
張貼留言