题10

题10

题目

Q:【2016 统考真题】若森林 有 15 条边、 25 个结点,则 包含树的个数是 ( )
A. 8
B. 9
C. 10
D. 11

分析

A:结点的度是指该结点的孩子数量, 每个结点与其每个孩子都由唯一的边相连, 因此树中所有结点的度数之和等于树中的边数之和。树中的结点 (除根外) 都有唯一的双亲, 因此结点数 等于边数之和加 1,即所有结点的度数之和加 1 。
森林是不相交的树的集合
每个树，都满足规律，他们的结点数比边数多1
宏观上，以森林的视角看，一共多了十个结点，这也就是每个树，固然的性质，多的这一个（和边数相比）结点所带来的
这和鸡兔同笼也还挺像的

解

C
解法 1: 树有一个重要性质,即在 个结点的树中有 条边,“那么对于每棵树,其结点数比边数多 1 ”。本题森林中的结点数比边数多 10 (即 ),显然共有 10 棵树。
解法 2: 仔细分析后发现此题也是考查图的性质: 生成树和生成森林。
对于图的生成树有一个重要的性质,即图中顶点数若为 ,则其生成树含有 条边。对比解法 1 中树的性质, 不难发现两种解法都用到了性质 “树中结点数比边数多 1 ”, 后面的分析如解法 1 。