若一个具有n个顶点和e条边的无向图是一个森林(n>e),则该森林必有( )棵树。
A. e
B. n
C. n-e
D. 1
一棵树的顶点数和边数差1,差几就有几棵树
设森林有k个树,k个树的节点数分别设为x1...xk,有x1+x2+...+xk=n,而每个树的边是节点数减一,即x-1,所以(x1-1)+(x2-1)+...+(xk-1)=e,化简可得k=n-e
有时候,可能过于关注局部特征,没能体会到宏观的特性。但是可⽤特值迅速解决:e条边全是⼀棵树的,那么这棵树有e+1个结点,剩下n-(e+1)个结点都不再形成边,即⼀个结点算⼀棵树。那么,共1+n-(e+1) = n-e棵树
C
用户登录可进行刷题及查看答案
登录后提交答案