若一个具有n个顶点和e条边的无向图是一个森林(n>e),则该森林必有( )棵树。
A. e
B. n
C. n-e
D. 1
假设森林中有3棵树,我们分别来看每棵树的顶点和边的情况,以及整体森林的情况。
第一棵树
● 有3个顶点(我们用A、B、C表示),边数为2条,即AB和BC。可以看到边数2 = 3 - 1 ,满足一棵树的边数e_1=n_1 - 1(这里n_1 = 3,e_1 = 2)。
第二棵树
● 有2个顶点(用D、E表示),边数为1条,即DE。边数1 = 2 - 1 ,满足一棵树的边数e_2=n_2 - 1(这里n_2 = 2,e_2 = 1)。
第三棵树
● 有1个顶点(用F表示),边数为0条。边数0 = 1 - 1 ,满足一棵树的边数e_3=n_3 - 1(这里n_3 = 1,e_3 = 0)。
整体森林
● 整个森林的顶点数n=n_1 + n_2 + n_3=3 + 2+1 = 6 。
● 边数e=e_1 + e_2 + e_3=2 + 1+0 = 3 。
● 树的棵数k = 3,同时n - e=6 - 3 = 3,符合公式k=n - e 。
一棵树的顶点数和边数差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
用户登录可进行刷题及查看答案
登录后提交答案