若一个具有n个结点、k条边的非连通无向图是一个森林(n>k),则该森林中必有(63)棵树。
【正确答案】 C
【答案解析】解析:假设该森林中有s棵树,分别为T1,T2,…,T s ,且每个T i 有n i 个结点,k i 条边(i=1, 2,…,s),由树的等价条件可知 k i =n i -1 则 k=k1+k2+…+k s =(n1-1)+(n2-1)+…+(n s -1)=n-s 故 s=n-k 所以该森林中必有n-k棵树。 另外,还可以这样考虑。首先,把n个单独的结点看成n棵树,然后再逐条加入边。显然,每加入一条边,则树的棵数就减1(把两棵树合并成一棵树),而题目告诉我们,总共有k条边,所以,树的总数为n-k。