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

Question

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

A．k

B．n

C．n-k

D．n+k

Answer 1

正确答案：C
解析：设该森林共有m棵树，每棵树有ni(1≤i≤m)个节点，依据树的性质有n=n1+n2+…+nmk=(n1-1)+(n2-1)+…+(nm-1)上面两式相减得n-k=1+1+…+1=m而m就是树的个数，所以该森林共有n-k棵树。