[理工] 107清大計科！

作者Aa841018 (andrew)

看板Grad-ProbAsk

標題[理工] 107清大計科！

時間Sun Jan 19 23:56:26 2020

https://i.imgur.com/CHkpyVS.jpg 請問 2.(a) 詳解做法是用degree算出edge，再用E=V-1這個公式，然後求出n 但我的想法是，利用2n+3n+n=6n(vertex) 2n+3n*2+n*3+1=11n+1 （branch+root) https://i.imgur.com/QOXiw7g.jpg 但這樣n<0 請問我哪裡做錯了嗎？ -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 110.28.64.164 (臺灣) ※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1579449388.A.A0E.html ※ 編輯: Aa841018 (110.28.64.164 臺灣), 01/20/2020 00:06:00

推 Zhu81801: degree會是邊數的兩倍 n應該是2 01/20 00:12

推 Zhu81801: 所以11n(total degree)/2=6n-1(點數-1) 01/20 00:18

→ MASAGA: branch+root那邊有點重複計算了吧 01/20 00:25

→ Aa841018: 恩，我知道，但那是解答的做法，我想請問我的做法有什 01/20 00:25

→ Aa841018: 麼問題？ 01/20 00:25

→ Aa841018: 請問哪裡重複計算了？ 01/20 00:26

推 mistel: 資結那個定理本質上就是e=v-1的衍生而已... 01/20 00:26

→ MASAGA: 這裡degree是相鄰點個數不是child個數 01/20 00:26

→ mistel: 而且你考卷上都寫這邊叫做leaf了，怎麼還會這樣算 01/20 00:27

→ MASAGA: 所以1個node叫A 他有兩個child A就會被多算一次 01/20 00:27

→ Aa841018: 恩…謝謝！ 01/20 00:29

→ MASAGA: 打完發現我敘述的有點怪XD 有不懂再說 01/20 00:32

推 mistel: 他說這是tree 沒說這是binary tree 所以也不能預設degree 01/20 00:33

→ mistel: 為3的點有幾個兒子 01/20 00:33

推 mistel: 所以這樣像資結那樣列式也不成立因為degree=3個點你不確 01/20 00:37

→ mistel: 定會不會有一個節點是root有三個兒子 01/20 00:37

→ mistel: 但在寫n*2時就預設了degree為3的點都不是root 01/20 00:38

推 mistel: https://i.imgur.com/JHvXBvo.jpg 反例 01/20 00:40