[理工] 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

继续阅读