[理工] 107清大計科！

看板Grad-ProbAsk作者 (andrew)時間4年前 (2020/01/19 23:56), 4年前編輯推噓6(6推 0噓 12→)
留言18則, 4人參與, 4年前最新討論串1/1
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
推
01/20 00:12, 4年前 , 1F
degree會是邊數的兩倍 n應該是2
01/20 00:12, 1F
推
01/20 00:18, 4年前 , 2F
所以11n(total degree)/2=6n-1(點數-1)
01/20 00:18, 2F
→
01/20 00:25, 4年前 , 3F
branch+root那邊有點重複計算了吧
01/20 00:25, 3F
→
01/20 00:25, 4年前 , 4F
恩，我知道，但那是解答的做法，我想請問我的做法有什
01/20 00:25, 4F
→
01/20 00:25, 4年前 , 5F
麼問題？
01/20 00:25, 5F
→
01/20 00:26, 4年前 , 6F
請問哪裡重複計算了？
01/20 00:26, 6F
推
01/20 00:26, 4年前 , 7F
資結那個定理本質上就是e=v-1的衍生而已...
01/20 00:26, 7F
→
01/20 00:26, 4年前 , 8F
這裡degree是相鄰點個數 不是child個數
01/20 00:26, 8F
→
01/20 00:27, 4年前 , 9F
而且你考卷上都寫這邊叫做leaf了，怎麼還會這樣算
01/20 00:27, 9F
→
01/20 00:27, 4年前 , 10F
所以1個node叫A 他有兩個child A就會被多算一次
01/20 00:27, 10F
→
01/20 00:29, 4年前 , 11F
恩…謝謝！
01/20 00:29, 11F
→
01/20 00:32, 4年前 , 12F
打完發現我敘述的有點怪XD 有不懂再說
01/20 00:32, 12F
推
01/20 00:33, 4年前 , 13F
他說這是tree 沒說這是binary tree 所以也不能預設degree
01/20 00:33, 13F
→
01/20 00:33, 4年前 , 14F
為3的點有幾個兒子
01/20 00:33, 14F
推
01/20 00:37, 4年前 , 15F
所以這樣像資結那樣列式也不成立 因為degree=3個點你不確
01/20 00:37, 15F
→
01/20 00:37, 4年前 , 16F
定會不會有一個節點是root有三個兒子
01/20 00:37, 16F
→
01/20 00:38, 4年前 , 17F
但在寫n*2時就預設了degree為3的點都不是root
01/20 00:38, 17F
推
01/20 00:40, 4年前 , 18F
反例
01/20 00:40, 18F
‣ 更多 Aa841018 的文章
文章代碼(AID): #1U97mieE (Grad-ProbAsk)