首页
题库
面试
求职
学习
竞赛
More+
所有博客
搜索面经/职位/试题/公司
搜索
我要招人
去企业版
登录 / 注册
首页
>
试题广场
>
若一个具有n个顶点,e条边的无向图是一个森林,则该森林中必有
[问答题]
若一个具有n个顶点,e条边的无向图是一个森林,则该森林中必有[$##$]棵树。
添加笔记
求解答(7)
邀请回答
收藏(8)
分享
纠错
5个回答
添加回答
3
进阶媛小吴
假设有x棵树,在树林中需要入x-1条边。 由树的定义得e=n-1打入得n-1=e+x-1 解得x=n-e
发表于 2019-10-17 19:28:06
回复(0)
1
牛客708621193号
如果某棵树中有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
发表于 2022-04-28 10:53:50
回复(0)
4
Tank.
有时候,可能过于关注局部特征,没能体会到宏观的特性。但是可⽤特值迅速解决:e条边全是⼀棵树的,那么这棵树有e+1个结点,剩下n-(e+1)个结点都不再形成边,即⼀个结点算⼀棵树。那么,共1+n-(e+1) = n-e棵树
发表于 2022-08-19 01:02:42
回复(0)
0
牛客274233608号
n-e
发表于 2020-11-15 18:38:29
回复(0)
0
梦溪1
n-e
发表于 2019-08-25 22:21:23
回复(0)
这道题你会答吗?花几分钟告诉大家答案吧!
提交观点
问题信息
树
图
上传者:
城市里的养猫者
难度:
5条回答
8收藏
6949浏览
热门推荐
相关试题
明明的随机数
数组
评论
(3691)
来自
华为研发工程师编程题
5.下列判断正确的是( )
资料分析
言语理解与表达
资料分析
评论
(1)
已知a
40
=...
京东
职能
2019
财务
保险
评论
(1)
《拳皇97》最后BOSS是谁?
游戏常识
评论
(1)
《魔兽世界》中,下列不属于玩家可以...
游戏常识
评论
(1)
扫描二维码,关注牛客网
意见反馈
下载牛客APP,随时随地刷题