首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
若无向图G=(V，E)中含8个顶点，为保证图G在任何情况下都是连通的，则需要的边数最少是( )。
若无向图G=(V，E)中含8个顶点，为保证图G在任何情况下都是连通的，则需要的边数最少是( )。
admin
2019-02-24
33
问题
若无向图G=(V，E)中含8个顶点，为保证图G在任何情况下都是连通的，则需要的边数最少是( )。
选项
A、7
B、21
C、22
D、28
答案
C
解析
本题考查图的基本概念。
要保证无向图G在任何情况下都是连通的，即任意变动图G中的边，G始终保持连通。首先需要图G的任意7个结点构成完全连通子图G
1
，需n(n-1)／2=7×(7-1)／2=21条边，然后再添加一条边将第8个结点与G
1
连接起来，共需22条边。
本题非常容易错误地选择选项A，主要原因是对“保证图G在任何情况下都是连通的”的理解，分析选项A，在图G中，具有8个顶点7条边并不能保证其一定是连通图，即有n-1条边的图不一定是连通图。
分析选项D，图G有8个顶点28条边，那么图G一定是无向完全图，无向完全图能保证其在任何情况下都是连通的，但是这不符合题目中所需边数最少的要求。
转载请注明原文地址:https://kaotiyun.com/show/9ECi777K
本试题收录于：
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
下列有关西欧封建社会的表述，错误的一项是()。
明代初年，废中书省，“六部”直接向皇帝负责，分割了宰相的权力，同时与“六部”合称为“七卿”，与六部地位不相上下的是()。
世界近代史上，世界经济发展经历了两次大的飞跃，即第一次工业革命和第二次工业革命。阅读下面两段材料，回答问题：材料一工业革命的主角——蒸汽机，是经验和科学相结合的产物。科学对工业革命的发展做出重大贡献。工场手工业的生产，主要依靠以人力和经
我国第一部系统的史学理论著作是（）。
阅读下面史料，回答问题：材料一各缔约国主力舰替换总吨位按照标准排水量计算不得超过如下：合众国525000吨；英帝国525000吨；法国175000吨；意大利175000吨；日本315000吨。
隋唐五代时期是中国古代商品经济发展史上的一个重要阶段，种类多，交换规模大，交换方式多。试回答问题：下列关于隋唐钱币的表述，不正确的是()
IP数据报的报文格式如下图所示。在没有选项和填充的情况下，报头长度域的值为()。
关于死锁的银行家算法是围绕“安全状态”的概念工作的。当系统预测到不安全状态时，就拒绝分配资源，但是，银行家算法要求的条件并不是必要的。例如，某系统有12个资源供进程P0、P1、P2使用。目前的分配情况如下：(1)请说明系统处于不安全状态；(2
在AOE网络中关键路径叙述正确的是()。
网络如图所示。链路旁边注明的数字代表链路的长度(假想单位)。试利用Dijk-stra算法求出从结点A到所有其他结点的最短路由。
随机试题
从生产与作业过程的空间组织的角度来看，单件小批生产类型的生产宜采用()
在侵权理论中，把二人以上实施的侵权行为，称为()。
非血管介入治疗常用的有
药品入库要严格执行验收制度，由经过专业培训并经考核合格后的验收人员严格按照规定的验收标准进行。以下“药品入库验收内容”中，表述不正确的是
下列各项属于招标采购计划主要内容的有()。
气体灭火系统中在吊顶内、活动地板下等隐蔽场所内的管道，可涂红色油漆色环，色环宽度不应小于()。
根据以下资料，回答问题。2014年，全国科技经费投入保持增长态势。其中，全国财政科学技术支出为6454．5亿元，比上年增加269．6亿元，增长4．4％；财政科学技术支出占当年国家财政支出的比重为4．25％。除此之外，全国投入研究与试验发展(R&D
反应时是
大厅里有40名应征者正在看说明书，总人数的1/3的人正在观看操作示范，还有20名避雨的人，在大厅内德人总共有()
Accordingtothepassage,FrederickⅡcarriedontheexperimentsto______.Whatisexceptionallyremarkableaboutchildistha
最新回复
(
0
)
