[理工]成大103數學 生成樹

看板Grad-ProbAsk作者 (馬吉叫我辦的)時間7年前 (2017/01/07 22:17), 編輯推噓4(4推 0噓 19→)
留言23則, 6人參與, 最新討論串1/1
這題不知道這樣寫對不對? http://i.imgur.com/MJpP7t6.jpg
-- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 115.82.151.204 ※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1483798679.A.E5C.html
→
01/07 22:27, , 1F
(c) 算式是對的 但b我不確定XD 怎不用cofactor算?
01/07 22:27, 1F
→
01/07 22:42, , 2F
想問原po怎麼算成15的?直接爆出來嗎
01/07 22:42, 2F
推
01/07 22:45, , 3F
我用矩陣算是40啦@@
01/07 22:45, 3F
→
01/07 22:49, , 4F
我直接算 因為不知道其他的方法><
01/07 22:49, 4F
→
01/07 22:59, , 5F
都忘記可以用矩陣算了，我算也是40
01/07 22:59, 5F
→
01/07 23:02, , 6F
要怎麼算?
01/07 23:02, 6F
→
01/07 23:05, , 8F
建一個類似adjacency matrix的矩陣，對角項填degree
01/07 23:05, 8F
→
01/07 23:05, , 9F
有邊相鄰的話填-1，否則填0，然後隨便找個cofactor就是
01/07 23:05, 9F
→
01/07 23:06, , 10F
spanning tree的個數
01/07 23:06, 10F
→
01/07 23:06, , 11F
我一直覺得這個方法超神奇
01/07 23:06, 11F
→
01/07 23:11, , 12F
真的超神奇的
01/07 23:11, 12F
推
01/07 23:15, , 13F
y大講的那個我記得課本叫做matrix-tree theorem
01/07 23:15, 13F
推
01/07 23:19, , 14F
對我來說用矩陣算我覺得是最安全的..
01/07 23:19, 14F
→
01/07 23:22, , 15F
驗算的時候還可以再挑另外一個cofactor算一次檢查相同
01/07 23:22, 15F
→
01/07 23:37, , 16F
那c就是10240000?
01/07 23:37, 16F
→
01/08 07:09, , 17F
我覺得應該是
01/08 07:09, 17F
推
01/08 10:21, , 18F
原來矩陣也可以算！！！這題的話我是用拆邊黏點
01/08 10:21, 18F
→
01/08 10:38, , 19F
拆邊黏點不是著色問題嗎?
01/08 10:38, 19F
→
01/08 10:52, , 20F
拆邊黏點也有spanning tree個數的版本XD
01/08 10:52, 20F
→
01/08 11:09, , 21F
可以分享一下解法嗎XD
01/08 11:09, 21F
→
01/08 11:38, , 22F
N(G)表示G的相異spanning tree的個數
01/08 11:38, 22F
→
01/08 11:38, , 23F
N(G)=N(G-e)+N(G.e)
01/08 11:38, 23F
‣ 更多 h9638512 的文章
文章代碼(AID): #1OSFYNvS (Grad-ProbAsk)