首页 > 试题广场 >

对于一个共有n个结点、K条边的森林，共有几棵树？

[单选题]

对于一个共有n个结点、K条边的森林，共有几棵树？ 

  • n - K
  • n - K + 1
  • n - K - 1
  • 不能确定
添加回答
推荐
liuyuhe头像 liuyuhe

解析：对于每一棵树来说，除去根结点，每一个结点上面都有一条边，因此边数e=n-1
则TotalEdgeNum=TotalNodeNum-TreeNum，所以TreeNum=TotalNodeNum-TotalEdgeNum=N-K，故此题选择A项。

编辑于 2020-01-06 14:53:02 回复(0)
胡迪尼头像 胡迪尼
如果某棵树中有N0个结点,K0条边,则N0 = k0 + 1
设森林中有m棵树,其结点数分别为n1,n2,n3,.,nm
相应地,各棵树的边数分别为k1,k2,k3,...km
显然：n1 = k1 + 1,n2 = k2 + 1,.,nm = km + 1 (1)
按照题设：
n1 + n2 + n3 +.+ nm = N (2)
k1 + k2 + k3 +.+ km = K (3)
将(1) 代入(2) 得：
(k1 + 1) + (k2 + 1) + (k3 + 1) + .+ (km + 1) = N
即：
k1 + k2 + k3 + ...+ km + 1 + 1 +.+ 1 = N
按照(3)：
K+ m= N
于是m = N - K
发表于 2020-03-26 11:06:49 回复(0)
heyJulian头像 heyJulian
由一颗树的性质：结点等于边+1【n= k+ 1】。
等价于 n - k =1。
故共有 n - k 棵树。
发表于 2020-07-05 20:44:59 回复(0)
柯浩头像 柯浩
树的一个性质为，节点数比边数多1，即n=e+1,故森林中节点数比边数多n-k，即有n-k棵树
发表于 2021-10-14 17:22:39 回复(0)
Simon..头像 Simon..
<p>构成森林中的所有树，节点总数不变，但是每多一棵树就会少一个节点，因为根结点头上没有天线。[手动狗头]</p>
发表于 2020-12-02 20:49:31 回复(1)
冻顶乌龙没有顶头像 冻顶乌龙没有顶
hellotest
发表于 2020-07-10 17:46:04 回复(0)
小小头像 小小
test
发表于 2020-07-10 17:24:25 回复(0)
天尊墨宇头像 天尊墨宇
选A
由一颗树的性质：结点等于边+1【n= k+ 1】。
等价于 n - k =1。
故共有 n - k 棵树。
编辑于 2020-07-07 10:22:51 回复(0)
提交观点

问题信息

树
上传者：城市里的养猫者
难度：
8条回答 14088浏览

热门推荐

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号