[理工] 105台大電機丙離散 tree qaswed101 PTT批踢踢實業坊

作者: qaswed101 (一一) 2018-02-04 17:20:30

https://i.imgur.com/wssAmya.jpg
想請問這題是怎麼推得的
上課的時候老師好像只有給答案
但是我不確定怎麼推出來的
謝謝

作者: lldavuull (小哲) 2018-02-04 17:47:00

v2+v0=n 2*v2=v2+v0-1 v2=v0-1 2v0-1=n v0=(n+1)/2

作者: taida (taida) 2018-02-04 17:50:00

假設degree1為l 剩下為n-l全部的degree總和至少為l+3(n-l)（因為剩下的node 的degree至少為3）然後上述會小於真正的degree加總也就是小於2e=2（v-1) 然後就可以推出來了

作者: lldavuull (小哲) 2018-02-04 17:56:00

換一種 E=(3*v3+v1)/2=v3+v1-1 v3=v1-2 n=v1+v3=2*v1-2v1=n/2+1

繼續閱讀