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

Question

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

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棵树。友情提示：该题如果清楚树的等价条件，可以很容易的解出。若不清楚，则无法下手。不过考生也可以画出一个具体的非连通无向图的森林，如：5个结点3条边2棵树的森林，也可帮助判断。抽象问题具体化是作选择题的一个重要方法。