若无向图G=(V，E)中含8个顶点，为保证图G在任何情况下都是连通的，则需要的边数最少是( )。

admin2019-02-24 26

问题若无向图G=(V，E)中含8个顶点，为保证图G在任何情况下都是连通的，则需要的边数最少是( )。

选项 A、7
B、21
C、22
D、28

答案C

解析本题考查图的基本概念。
要保证无向图G在任何情况下都是连通的，即任意变动图G中的边，G始终保持连通。首先需要图G的任意7个结点构成完全连通子图G₁，需n(n-1)／2=7×(7-1)／2=21条边，然后再添加一条边将第8个结点与G₁连接起来，共需22条边。
本题非常容易错误地选择选项A，主要原因是对“保证图G在任何情况下都是连通的”的理解，分析选项A，在图G中，具有8个顶点7条边并不能保证其一定是连通图，即有n-1条边的图不一定是连通图。
分析选项D，图G有8个顶点28条边，那么图G一定是无向完全图，无向完全图能保证其在任何情况下都是连通的，但是这不符合题目中所需边数最少的要求。

转载请注明原文地址:https://kaotiyun.com/show/9ECi777K

本试题收录于：计算机408题库学硕统考专业分类

计算机408

学硕统考专业

相关试题推荐

随机试题

最新回复(0)

若无向图G=(V，E)中含8个顶点，为保证图G在任何情况下都是连通的，则需要的边数最少是( )。

计算机408

学硕统考专业

1923年纳粹党魁希特勒发动了“啤酒馆暴动”，对此叙述不正确的一项是()。

北宋时期，由于原有的市坊制度被打破，因此北宋政府控制商人和商业主要通过()。

宋代至清代我国书籍印刷的主要方式是()

在西欧列强海外殖民扩张进程中，各国之间相互争夺海上霸权。18世纪末，英国在争霸中取得胜利的根本原因在于()

论述公元前6世纪至公元1世纪佛教的形成与传播。

印度列国时代出现了16个国家，其中大部分是王国，只有少数的共和国。下列属于共和国的是()。

某网络的拓扑结构由下图所示，其中顶点表示路由器。该网络的路由器采用了链路状态路由算法，在某一时刻各个路由器发送的链路状态如下：A：B(1)，D(3)B：A(1)，D(1)，C(3)，E(5)C：B(3)，D(1)D：A(3)，B(1

就绪队列中有n个进程等待使用一个CPU，那么，如果采用不同的调用算法，就有()种调度顺序。

已知加权有向图G如下，回答下列问题：(1)画出该有向图G的邻接矩阵；(2)试利用Dijkstra算法求G中从顶点a到其他各顶点间的最短路径，并给出求解过程。

关于以太网交换机，下面的论述中不正确的是()。

openedinjury

颌骨畸形的早期矫治一般在

属于纤维素性炎的是

秦统治者总结前代法律实施方面的经验，结合本朝特点，形成了一些刑罚适用原则。对于秦律原则的相关表述，下列哪一选项是正确的?(2017年卷一16题)

证券经营机构将自营业务与经纪业务混合操作所受到的最严厉的处罚是()

某城市的机动车车牌号由大写英文字母和0—9十个数字组成，共五位。若交通局规定第一位必须是字母，其余四位均为数字，请你计算尾号是0的机动车牌号有()个。

下列诗句未涉及秋天的是（）。

包豪斯设计学院位于()。

Celebrityworshipisnowintherisingandsomeyoungsterscannotresistjumpingonthewagon.Giveyourcommentonthisphenome

TheMonaLisaisshowingherage,museumcurators(馆长)inParissaidwhileannouncingascientificstudyofthe500-year-oldmas