作者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://webptt.com/m.aspx?n=bbs/Grad-ProbAsk/M.1579449388.A.A0E.html
※ 編輯: Aa841018 (110.28.64.164 臺灣), 01/20/2020 00:06:00
1F：推 Zhu81801: degree會是邊數的兩倍 n應該是2 01/20 00:12
2F：推 Zhu81801: 所以11n(total degree)/2=6n-1(點數-1) 01/20 00:18
3F：→ MASAGA: branch+root那邊有點重複計算了吧 01/20 00:25
4F：→ Aa841018: 恩，我知道，但那是解答的做法，我想請問我的做法有什 01/20 00:25
5F：→ Aa841018: 麼問題？ 01/20 00:25
6F：→ Aa841018: 請問哪裡重複計算了？ 01/20 00:26
7F：推 mistel: 資結那個定理本質上就是e=v-1的衍生而已... 01/20 00:26
8F：→ MASAGA: 這裡degree是相鄰點個數 不是child個數 01/20 00:26
9F：→ mistel: 而且你考卷上都寫這邊叫做leaf了，怎麼還會這樣算 01/20 00:27
10F：→ MASAGA: 所以1個node叫A 他有兩個child A就會被多算一次 01/20 00:27
11F：→ Aa841018: 恩…謝謝！ 01/20 00:29
12F：→ MASAGA: 打完發現我敘述的有點怪XD 有不懂再說 01/20 00:32
13F：推 mistel: 他說這是tree 沒說這是binary tree 所以也不能預設degree 01/20 00:33
14F：→ mistel: 為3的點有幾個兒子 01/20 00:33
15F：推 mistel: 所以這樣像資結那樣列式也不成立 因為degree=3個點你不確 01/20 00:37
16F：→ mistel: 定會不會有一個節點是root有三個兒子 01/20 00:37
17F：→ mistel: 但在寫n*2時就預設了degree為3的點都不是root 01/20 00:38