首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
若一个具有n个结点、k条边的非连通无向图是一个森林(n>k),则该森林中必有(63)棵树。
若一个具有n个结点、k条边的非连通无向图是一个森林(n>k),则该森林中必有(63)棵树。
admin
2019-05-23
12
问题
若一个具有n个结点、k条边的非连通无向图是一个森林(n>k),则该森林中必有(63)棵树。
选项
A、k
B、n
C、n-k
D、n+k
答案
C
解析
假设该森林中有s棵树,分别为T1,T2,…,T
s
,且每个T
i
有n
i
个结点,k
i
条边(i=1, 2,…,s),由树的等价条件可知
k
i
=n
i
-1
则
k=k1+k2+…+k
s
=(n1-1)+(n2-1)+…+(n
s
-1)=n-s
故
s=n-k
所以该森林中必有n-k棵树。
另外,还可以这样考虑。首先,把n个单独的结点看成n棵树,然后再逐条加入边。显然,每加入一条边,则树的棵数就减1(把两棵树合并成一棵树),而题目告诉我们,总共有k条边,所以,树的总数为n-k。
转载请注明原文地址:https://kaotiyun.com/show/UfTZ777K
本试题收录于:
数据库系统工程师上午基础知识考试题库软考中级分类
0
数据库系统工程师上午基础知识考试
软考中级
相关试题推荐
(2009上系分)极限编程是一种重要的敏捷开发方法,包含策划、设计、编码和测试四个框架活动的规则和实践。下面关于极限编程的叙述,错误的是______。
(2006下项管)极限编程技术XP适用于______。
(2010上集管)在评标过程中,______是不符合招标投标法要求的。
(2007上系分)UML提供了5种对系统动态方面建模的图,其中______(1)对系统行为组织和建模;______(2)对系统功能建模,它强调对象之间的控制流;______(3)之间是同构的。(2)
(2011上集管)根据下面的UML类图,以下叙述中______是不正确的。
(2010上监理)入侵检测系统使用入侵检测技术对网络和系统进行监视,并根据监视结果采取不同的处理,最大限度降低可能的入侵危害。以下关于入侵检测系统的叙述,不正确的是______。
(2010下项管)在系统建设后期,建设方考虑到系统运维管理问题,希望增加8课时的IT服务管理方面的知识培训,承建方依此要求进行了范围变更。在对范围变更进行验证时,验证准则是______。
(2011下项管)某公司从甲地向丁地远送物资,运送过程中先后需要经过乙、丙两个中转站,其中乙中转站可以选择乙1和乙2两个可选地点,丙中转站可以选择丙l、丙2和丙3三个可选地点,各相邻两地之间的距离如表所示,则甲地到丁地之间的最短距离为______。
(2008上系分)某轴承厂有甲、乙、丙三个车间,各车间生产的轴承数量分别占全厂的40%、30%、30%,各车间的次品率分别为3%、4%、5%(正品率分别为97%、96%、95%)。以上叙述可以图示如下在图中,从“厂”结点出发选择三个车间产品的概
数据库系统运行的基本工作单位是事务。事务通常以BEGINTRANSACTION语句开始,以COMMIT或ROLLBACK吾句结束。COMMIT表示(26),ROLLBACK表示(27)。从终端用户的角度看,事务是一个(28)。在数据库的并发控制中
随机试题
设λ=2是n阶方阵A的一个特征且|A|≠0,则n阶方阵B=A3一3E+A-1必有特征值_______.
三五之夜,明月半墙,桂影斑驳,风移影动,珊珊阿爱。
常用的苯扎溴铵消毒液化学名称为
重型肝炎为抑制大肠杆菌、减少游离氨及其它毒素的形成可使用药物:重型肝炎补充营养及增强免疫力可使用药物:
我国法定的职业性肿瘤包括下列哪一种
急性高原反应应采取下面哪些措施
开创内伤杂病辨证体系的医书是
患儿,男,7岁。被诊断为细菌性痢疾,经治疗目前临床症状已消失,家长询问何时可以上学,护士指导正确的是
样本空间中特定的结果或其中的某一个组合叫作( )。
()是产生在法律基础上的损害赔偿责任,它是由于人们的过失或侵权行为导致他人的财产毁损或人身伤亡,在合同、道义、法律上负有经济赔偿责任的风险。
最新回复
(
0
)