[理工] 105台大電機丙 離散 tree

[qaswed101 (一一)]

https://i.imgur.com/wssAmya.jpg
想請問這題是怎麼推得的

上課的時候老師好像只有給答案
但是我不確定怎麼推出來的

謝謝

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 101.13.50.203
※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1517736033.A.29D.html
推 lldavuull: v2+v0=n 2*v2=v2+v0-1 v2=v0-1 2v0-1=n v0=(n+1)/2
推 taida: 假設degree1為l 剩下為n-l全部的degree總和至少為l+3(n-l)
→ taida:  （因為剩下的node 的degree至少為3）
→ taida: 然後上述會小於真正的degree加總 也就是小於2e=2（v-1) 然
→ taida: 後就可以推出來了
→ lldavuull: 換一種 E=(3*v3+v1)/2=v3+v1-1 v3=v1-2 n=v1+v3=2*v1-2
→ lldavuull: v1=n/2+1
原來如此 太感謝了！
※ 編輯: qaswed101 (101.13.50.203), 02/04/2018 18:03:57
推 sssxyz11: 可是這題他沒有說是binary tree欸，這樣解法有瑕疵吧
→ DLHZ: binary tree一定是最少的情況 可以隨意想像一下非二元跟二元
→ DLHZ: 的情況 在知道最佳解必是二元後由上述方法推得