问题 单项选择题

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

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。

单项选择题 A1型题
单项选择题