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

admin2019-06-12 25

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

选项 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棵树。

转载请注明原文地址:https://kaotiyun.com/show/apRZ777K

软件设计师上午基础知识考试

相关试题推荐

随机试题

最新回复(0)