首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
若一个具有n个结点、k条边的非连通无向图是一个森林(n>k),则该森林中必有(63)棵树。
若一个具有n个结点、k条边的非连通无向图是一个森林(n>k),则该森林中必有(63)棵树。
admin
2019-05-23
27
问题
若一个具有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
数据库系统工程师上午基础知识考试
软考中级
相关试题推荐
(2006上系管)下列选项中,符合UML动态建模机制的是______。
(2007下软设)在下面的用例图(UseCaseDiagram)中,X1、X2和X3表示______(1),已知UC3是抽象用例,那么X1可通过______(2)用例与系统进行交互。并且,用例______(3)是UC4的可选部分,用例______(4)是
(2014下项管)在UML图形上,把一个泛化关系画成______。
(2006下系分)用例从用户角度描述系统的行为。用例之间可以存在一定的关系。在“某图书馆管理系统”用例模型中,所有用户使用系统之前必须通过“身份验证”,“身份验证”可以有“密码验证”和“智能卡验证”两种方式,则“身份验证”与“密码验证”和“智能卡验证”之间
(2005上项管)项目小组建设对于项目的成功很重要,因此,项目经理想考察项目小组工作的技术环境如何,有关信息可以在______中找到。
(2005下项管)在项目进行过程中,一个开发人员接收到某个用户的电话,用户表明在系统中存在一个问题并要求更改,这个开发人员应该______。
(2007下软设)UML中有多种类型的图,其中,______(1)对系统的使用方式进行分类,______(2)显示了类及其相互关系,______(3)显示人或对象的活动,其方式类似于流程图,通信图显示在某种情况下对象之间发送的消息,______(4)与通信
(2006下监理)下列的描述中,______不是项目特点。
(2011下项管)下列描述中,______不是软件体系结构研究的内容。
(2012上项管)某大型布线项目由甲、乙两个项目组成。甲项目场地准备需3天,乙项目场地准备需2天;甲项目施工需5天,乙项目施工需4天。两个项目的场地准备都需要一台专用设备。在只有一台可用的专用设备的情况下,此大型项目至少需要______天才能完成。
随机试题
氟喹诺酮类药物的抗菌作用机制是
虚证泄泻的特征是实证泄泻的特征是
工程项目沟通方式包括书面正式的、书面非正式的、口头正式的和口头非正式的沟通。下列关于沟通方式的说法正确的是()。
下列说法正确的是( )。
支付令是人民法院依照()规定的督促程序,根据债权人的申请,向债务人发出的限期履行给付金钱或有价证券的法律文书。
转变城乡二元结构是解决“三农”问题的重点和关键。()
国家主义派
一般不公开审判的案件是()。
From:JosieRobertsTo:KurtBowmanDate:July24Subject:Re:BoothReservationAttachment:ServicesandFacilitiesDearMr.
MostAmericansspendfarmoreoftheirleisuretimewiththemassmediathaninanyotheroccupation.Inaddition,mostofushe
最新回复
(
0
)