[理工] 離散 91/100 成大工科 連通

看板Grad-ProbAsk作者時間8年前 (2017/04/20 20:04), 8年前編輯推噓0(0推 0噓 10→)
留言10則, 2人參與, 最新討論串1/1
如圖: http://i.imgur.com/jPjIzHH.png
我想問一下有大大知道這題的解法嗎?? 我很納悶為什麼是 A 加到 A^(n-1) 感謝!!! -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 61.230.126.230 ※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1492689847.A.B6F.html
→
04/20 21:46, , 1F
A^k 裡的aij表示從i點到j點走k步的方法數
04/20 21:46, 1F
→
04/20 21:46, , 2F
所以應該是則表示走n-1步都到不了
04/20 21:46, 2F
是因為 最少形成連通圖的路徑是樹狀(邊數 = 點 - 1)結構嗎 ? 所以若要判斷這圖是否為連通圖 就是要加到最少邊數的連通圖? ※ 編輯: jerry900287 (61.230.126.230), 04/21/2017 09:33:28 ※ 編輯: jerry900287 (61.230.126.230), 04/21/2017 09:33:59
→
04/21 18:31, , 3F
我的想法是G=(V,E), ∣V∣=n 若有一點a不重複走了n-1
04/21 18:31, 3F
→
04/21 18:31, , 4F
步都到不了b，則a，b一定不相連
04/21 18:31, 4F
→
04/21 18:34, , 5F
我不去確定你說的樹狀結構是指什麼，所以我無法判斷你
04/21 18:34, 5F
→
04/21 18:34, , 6F
的想法對或錯
04/21 18:34, 6F
→
04/21 21:16, , 7F
遞移包
04/21 21:16, 7F
→
04/21 21:38, , 8F
剛剛讀到你說的樹狀結構了，我覺得用這樣的想法怪怪
04/21 21:38, 8F
→
04/21 21:38, , 9F
的，因為如果要說是不連通，不能用最少邊數去推導
04/21 21:38, 9F
→
04/21 21:39, , 10F
所以n大說的應該才是本題的key point
04/21 21:39, 10F
OK 好的 感謝!! 等我讀到遞移包我再來看看 ※ 編輯: jerry900287 (61.230.126.230), 04/21/2017 22:18:32
‣ 更多 jerry900287 的文章
文章代碼(AID): #1O-AEtjl (Grad-ProbAsk)