首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
若无向图G=(V，E)中含8个顶点，为保证图G在任何情况下都是连通的，则需要的边数最少是( )。
若无向图G=(V，E)中含8个顶点，为保证图G在任何情况下都是连通的，则需要的边数最少是( )。
admin
2019-02-24
51
问题
若无向图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://www.kaotiyun.com/show/9ECi777K
本试题收录于：
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
论述欧洲一体化进程及其影响。
第一次国共合作采取了共产党员以个人身份加入国民党的“党内合作”方式。最早提出这种方式的是()。
二次大战后，主要资本主义国家经历了增长时期，首先开始这个进程的国家是()。
洋务运动期间，军事企业主要采取的方式是()。
下列关于社会大分工不正确的说法是()。
IP数据报的报文格式如下图所示。在没有选项和填充的情况下，报头长度域的值为()。
某网络的拓扑结构由下图所示，其中顶点表示路由器。该网络的路由器采用了链路状态路由算法，在某一时刻各个路由器发送的链路状态如下：A：B(1)，D(3)B：A(1)，D(1)，C(3)，E(5)C：B(3)，D(1)D：A(3)，B(1
已知加权有向图G如下，回答下列问题：(1)画出该有向图G的邻接矩阵；(2)试利用Dijkstra算法求G中从顶点a到其他各顶点间的最短路径，并给出求解过程。
假定一台计算机的显示存储器用DRAM芯片实现，若要求显示分辨率为1600×1200，颜色深度为24位，帧频为85Hz，显存总带宽的50％用来刷新屏幕，则需要的显存总带宽至少约为____。
现有一个解决无向连通图的最小生成树的一种方法如下：将图中所有边按权重从大到小排序为(e1，e2．…，em)；i＝l；while(所剩边数>＝顶点数){从图中删去ei；若图不再连通，则恢复ei；i＝i＋l；
随机试题
《礼记》是一部()。
Igavehimthebook,butdemandedthathe______ittomeinaweek.
A．血栓性浅静脉炎B．血栓性深静脉炎C．游走性浅静脉炎D．血栓闭塞性脉管炎E．动脉硬化闭塞症
160日龄产蛋鸡群2天内产蛋下降30%，大部分鸡呼吸困难，流鼻涕，打喷嚏；部分鸡结膜潮红，眶下窦水肿，有干酪样分泌物。剖检见上呼吸道黏膜充血、肿胀，表面覆盖大量黏液，其他脏器无明显病变。该病可能是
关于妊娠子宫的生理性变化，正确的是()
甲公司从国外进口一批货物，根据《联合国国际货物销售合同公约》，关于货物检验和交货不符合同约定的问题，下列说法正确的是：(2013年卷一99题，不定项)
下列物质在水溶液中能大量共存的是()。
假定系统拥有某类资源10个。在该系统上运行的所有作业，其对该类资源的需求量不会超过2个。为了提高资源利用率，我们打算对这种资源采用动态分配，但用限制系统中并发执行的作业数来防止发生死锁。你认为作业调度允许并发执行的最大作业数应是()。
美国授予发明者的专利数量由1971年的56000项下降到1978年的45000项。美国在研究和开发方面的投入在1964年到达其顶峰——占GNP的3%，而在1978年只是2%，在这期间，研究和开发费用占GNP的比重一直在下降。同一时期，西德和日本却增加了它
计算，从z轴正向看，L是逆时针方向．
最新回复
(
0
)
