2. 计算机
  3. 若一个具有n个结点、k条边的非连通无向图是一个森林(n＞k)，则该森林中必有(63)棵树。

若一个具有n个结点、k条边的非连通无向图是一个森林(n＞k)，则该森林中必有(63)棵树。

admin2019-05-23  24
问题 若一个具有n个结点、k条边的非连通无向图是一个森林(n＞k)，则该森林中必有(63)棵树。
选项 A、k
B、n
C、n-k
D、n+k
答案C
解析 假设该森林中有s棵树，分别为T1，T2，…，Ts，且每个Ti有ni个结点，ki条边(i=1， 2，…，s)，由树的等价条件可知
   ki＝ni-1
   则
   k＝k1+k2+…+ks＝(n1-1)+(n2-1)+…+(ns-1)＝n-s
   故
   s=n-k
   所以该森林中必有n-k棵树。
   另外，还可以这样考虑。首先，把n个单独的结点看成n棵树，然后再逐条加入边。显然，每加入一条边，则树的棵数就减1(把两棵树合并成一棵树)，而题目告诉我们，总共有k条边，所以，树的总数为n-k。
转载请注明原文地址:https://kaotiyun.com/show/UfTZ777K
本试题收录于： 数据库系统工程师上午基础知识考试题库软考中级分类
0

数据库系统工程师上午基础知识考试

软考中级

相关试题推荐
随机试题
最新回复(0)