作者qaswed101 (一一)
看板Grad-ProbAsk
标题[理工] 105台大电机丙 离散 tree
时间Sun Feb 4 17:20:30 2018
https://i.imgur.com/wssAmya.jpg
想请问这题是怎麽推得的
上课的时候老师好像只有给答案
但是我不确定怎麽推出来的
谢谢
--
※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 101.13.50.203
※ 文章网址: https://webptt.com/cn.aspx?n=bbs/Grad-ProbAsk/M.1517736033.A.29D.html
1F：推 lldavuull: v2+v0=n 2*v2=v2+v0-1 v2=v0-1 2v0-1=n v0=(n+1)/202/04 17:47
2F：推 taida: 假设degree1为l 剩下为n-l全部的degree总和至少为l+3(n-l)02/04 17:50
3F：→ taida: （因为剩下的node 的degree至少为3）02/04 17:50
4F：→ taida: 然後上述会小於真正的degree加总 也就是小於2e=2（v-1) 然02/04 17:52
5F：→ taida: 後就可以推出来了02/04 17:52
6F：→ lldavuull: 换一种 E=(3*v3+v1)/2=v3+v1-1 v3=v1-2 n=v1+v3=2*v1-202/04 17:56
7F：→ lldavuull: v1=n/2+102/04 17:56
原来如此 太感谢了！
※ 编辑: qaswed101 (101.13.50.203), 02/04/2018 18:03:57
8F：推 sssxyz11: 可是这题他没有说是binary tree欸，这样解法有瑕疵吧 02/06 09:51
9F：→ DLHZ: binary tree一定是最少的情况 可以随意想像一下非二元跟二元 12/13 12:17
10F：→ DLHZ: 的情况 在知道最佳解必是二元後由上述方法推得 12/13 12:18