若一个具有n个结点、k条边的非连通无向图是一个森林(n>k),则该森林中必有(63)棵树。A.kB.nC.n－kD.n

Question

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

A．k

B．n

C．n-k

D．n+k

Answer 1

正确答案：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。