A-A+
若一个具有n个结点 k条边的非连通无向图是一个森林(n k) 则该森林中必有(58)棵树。A
问题详情
若一个具有n个结点、k条边的非连通无向图是一个森林(n,k),则该森林中必有(58)棵树。
A.k
B.n
C.n-k
D.n+k请帮忙给出正确答案和分析,谢谢!
参考答案
正确答案:C
解析:假设该森林中有s棵树:T1,T2...,TS,且每个Ti有ni个结点,ki条边(i=1,2,...,S),由树的等价条件可知:ki=ni-1,则k=k1+k2+...+ks:(n1-1)+(n2-1)+...+(ns-1)=n-s,故s=n-k,所以该森林中必有n-k棵树。友情提示:该题如果清楚树的等价条件,可以很容易的解出。若不清楚,则无法下手。不过考生也可以画出一个具体的非连通无向图的森林,如:5个结点3条边2棵树的森林,也可帮助判断。抽象问题具体化是作选择题的一个重要方法。