题目
一棵树有2个2度顶点,1个3度顶点,3个4度顶点,其余顶点都是树叶,则树叶数目为()A. 5B. 7C. 8D. 9
一棵树有2个2度顶点,1个3度顶点,3个4度顶点,其余顶点都是树叶,则树叶数目为()
A. 5
B. 7
C. 8
D. 9
题目解答
答案
D. 9
解析
本题考查树的性质以及握手定理的应用。解题的关键思路是利用树的顶点数和边数的关系,结合握手定理建立方程来求解树叶的数目。
设树叶的数目为 $x$。
- 计算树的顶点数 $n$:
已知树中有 $2$ 个 $2$ 度顶点,$1$ 个 $3$ 度顶点,$3$ 个 $4$ 度顶点,以及 $x$ 个树叶(树叶的度数为 $1$),那么树的顶点数 $n$ 为各类顶点数之和,即 $n = 2 + 1 + 3 + x=6 + x$。 - 计算树的边数 $m$:
根据树的性质,对于任何一棵树,其边数 $m$ 比顶点数 $n$ 少 $1$,所以边数 $m=n - 1=(6 + x)-1 = 5 + x$。 - 应用握手定理:
握手定理指出,在任何无向图中,所有顶点的度数之和等于边数的 $2$ 倍,即 $\sum_{i = 1}^{n}d(v_i)=2m$。
在本题中,$2$ 个 $2$ 度顶点的度数和为 $2\times2 = 4$;$1$ 个 $3$ 度顶点的度数为 $3$;$3$ 个 $4$ 度顶点的度数和为 $3\times4 = 12$;$x$ 个树叶的度数和为 $x\times1=x$。
所以所有顶点的度数之和为 $4 + 3+12 + x=19 + x$。
又因为边数 $m = 5 + x$,根据握手定理可得 $19 + x = 2\times(5 + x)$。 - 解方程求解 $x$:
对 $19 + x = 2\times(5 + x)$ 进行求解:
$\begin{align*}19 + x&=10 + 2x\\2x - x&=19 - 10\\x&=9\end{align*}$