结构推理
设图G是一棵树，它有n
2
个2次分枝结点，n
3
个3次分枝结点，…，n
k
个k次分枝结点，求G中叶结点数．
【正确答案】
设G中叶结点数为x
则G中结点数n=x+n
2
+n
3
+…+n
k
，
边数m=n-1=(z+n
2
+n
3
+…+n
k
)-1，而所有结点度数之和∑
i=
n
deg(v
i
)=2m，
因此有：z·1+n
2
·2+…+，2n
k
·k=2·(x+n
2
+…+n
k
)-2x
x=n
3
+2n
1
+…+(k-2)n
k
+2．
【答案解析】
本题综合了图、树(一种特殊的图)中有关结点、边、度数的概念和相互之间的关系．例如，m=n-1是树满足的关系式，图就未必满足，而满足m=n-1的图也未必是树．
提交答案
关闭