问题 单项选择题

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

A.k

B.n

C.n-k

D.n+k

答案

参考答案:C

解析:

设该森林共有m棵树,每棵树有ni(1≤i≤m)个节点,依据树的性质有

n=n1+n2+…+nm

k=(n1-1)+(n2-1)+…+(nm-1)

上面两式相减得

n-k=1+1+…+1=m

而m就是树的个数,所以该森林共有n-k棵树。

判断题
论述题