首页 > 试题广场 >

若一个具有N个结点，M条边的无向图构成一个森林，(NM)，

[单选题]
若一个具有N个结点，M条边的无向图构成一个森林，(N>M)， 则该森林必有(  )棵树。

  • M
  • N
  • N-M
  • 12
添加回答
推荐
Jino.头像 Jino.
选C。
设该森林共有m棵树，每棵树有ni(1≤i≤m)个节点，依据树的性质有
N=n1+n2+…+nm
M=(n1-1)+(n2-1)+…+(nm-1)
上面两式相减得
N-M=1+1+…+1=m
而m就是树的个数，所以该森林共有N-M棵树。
编辑于 2019-12-10 14:21:18 回复(0)
ltq～头像 ltq～
假设最初的图只有N个结点，即有N棵树，每增加一条边，则少一棵树，若有M条边，则剩N-M棵树
发表于 2020-05-02 22:12:05 回复(0)
白驹之过隙头像 白驹之过隙
选C。
利用类比举例法：
假设有三个（N=3）顶点，如果有两条边（M=2）的无向图构成森林的话。
  • 一个顶点作为根节点，另外两个作为子结点，构成一棵树（N-M=1）

带入选项中，可以得出C正确。

发表于 2019-12-09 19:35:50 回复(0)
天尊墨宇头像 天尊墨宇
选C。
设该森林共有m棵树，每棵树有ni(1≤i≤m)个节点，依据树的性质有
N=n1+n2+…+nm
M=(n1-1)+(n2-1)+…+(nm-1)
上面两式相减得
N-M=1+1+…+1=m
而m就是树的个数，所以该森林共有N-M棵树。
发表于 2020-07-01 09:35:59 回复(0)
yanl_头像 yanl_
根据一棵树的边数+1=结点数。
可以知道，每多一棵树，结点数就少一个。
即，
一棵树时，边数 = 结点数-1
两棵树时，边数 = 结点数-2
….
n棵树时，边数 = 结点数-n
发表于 2020-03-07 21:35:34 回复(0)
提交观点

问题信息

树
上传者：zsw3
难度：
5条回答 4179浏览

热门推荐

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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