首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
若无向图G=(V,E)中含8个顶点,为保证图G在任何情况下都是连通的,则需要的边数最少是( )。
若无向图G=(V,E)中含8个顶点,为保证图G在任何情况下都是连通的,则需要的边数最少是( )。
admin
2019-02-24
31
问题
若无向图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
学硕统考专业
相关试题推荐
典型的西欧封建庄园对农民采用的剥削方式是()。
19世纪中期,德意志资产阶级迫切要求实现国家的统一,其首要的目的是()。
第一次国共合作采取了共产党员以个人身份加入国民党的“党内合作”方式。最早提出这种方式的是()。
周王室的两大官僚系统是()。
下列选项中,控制了西域政权的是()。
罗马法的集大成《查士丁尼民法大全》产生的时间是在()。
在平衡二叉树中的每个结点上增设一个Lsize域,其值为它的左子树中的结点个数加1,试写一个时间复杂度为O(logn)的算法,确定树中第k个结点的位置。
图的D搜索类似于BFS,不同之处在于使用栈代替BFS中的队列,入/出队列的操作作为入/出栈的操作,即当一个顶点的所有邻接结点被搜索后,下一个搜索出发点应该是最近入栈(栈顶)的顶点。(1)用邻接表作为存储结构,写一个D搜索算法;(2)用D搜索方法
下图所示为双总线结构机器的数据通路,IR为指令寄存器,PC为程序计数器(具有自增功能),M为主存(受R/W信号控制),AR为地址寄存器,DR为数据缓冲寄存器,ALU由加、减控制信号决定完成何种操作,控制信号G控制的是一个门电路。另外,线上标注有小圈表示有控
现有一个解决无向连通图的最小生成树的一种方法如下:将图中所有边按权重从大到小排序为(e1,e2.…,em);i=l;while(所剩边数>=顶点数){从图中删去ei;若图不再连通,则恢复ei;i=i+l;
随机试题
A.胸膜腔穿刺排气B.胸壁大块切除重建术C.心包引流D.开胸或胸腔镜手术探查E.气管插管呼吸机辅助呼吸男性,30岁,1周前因外伤致左侧气胸伴少量积液,行胸腔闭式引流术,目前复查胸片提示左肺复张不全,引流管内仍有较多气泡溢出。正确的处理是
对乙酰氨基酚与三氯化铁试液作用显
足月儿,G4P1,出生时一般情况好,无青紫窒息,纯母乳喂养,生后12h即出现黄疸,其母孕期体健,前3胎中,第1胎为人工流产,第2、3胎在生后均因黄疸死亡。检查发现患儿血红蛋白100g/L,血清胆红素386μmol/L,此时下列哪项检查最重要
血液病患者的白细胞低于下列哪项时需进行保护性隔离
施工单位应在()对建筑物垂直度和标高进行实测并记录,填写建筑物垂直度、标高测量记录,报监理单位审核。
陶瓷器是陶器制品和瓷器制品的总称。陶器是用黏土成型,经700℃—800℃的炉温焙烧而成的日用品和陈设品。陶器的发明,是人类历史上最早通过火的作用使一种物质改变成另一物质的创造性活动。陶器的出现标志着新石器时代的开始,使人类的定居生活更加稳固。我国
电子邮件对于()相当于()对于道路
最惠国待遇[南京大学2011国际商务硕士;中央财经大学2011国际商务硕士;浙江工商大学2011国际商务硕士;南京理工大学2011国际商务硕士;上海财经大学2011国际商务硕士]
下列函数定义中,会出现编译错误的是
Thereisacloserrelationshipbetweenmoralsandarchitectureandinteriordecoration(1)_____wesuspect.Huxleyhas(2)_____th
最新回复
(
0
)