单选题
若一个具有n个节点、k条边的非连通无向图是一个森林(n>k),则该森林中必有
(19)
棵树。
A、
k
B、
n
C、
n-k
D、
n+k
【正确答案】
C
【答案解析】
[分析] 设该森林共有m棵树,每棵树有n
i
(1≤i≤m)个节点,依据树的性质有
n=n
1
+n
2
+…+n
m
k=(n
1
-1)+(n
2
-1)+…+(n
m
-1)
上面两式相减得
n-k=1+1+…+1=m
而m就是树的个数,所以该森林共有n-k棵树。
提交答案
关闭