问题
单项选择题
若一个具有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。