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