Question

设一棵无向树,有3个结点次数为2,1个结点次数为3,2个结点次数为4,则它有_________个结点次数为1

Answer 1

设度数为1的结点有x个,则结点个数共 x+3+1+2个.由于树的边数是结点数减1,故树的边数为x+3+1+2-1,该树的所有结点总度数总和为

x+3*2+1*3+2*4

结点总度数等于边数的2倍,故得方程

x+3*2+1*3+2*4=(x+3+1+2-1)

解得 x+17=2(x+5)

x=7

故度数为1的结点有7个.