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

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

admin2019-02-24  22
问题 若无向图G=(V，E)中含8个顶点，为保证图G在任何情况下都是连通的，则需要的边数最少是(    )。
选项 A、7
B、21
C、22
D、28
答案C
解析 本题考查图的基本概念。
    要保证无向图G在任何情况下都是连通的，即任意变动图G中的边，G始终保持连通。首先需要图G的任意7个结点构成完全连通子图G1，需n(n-1)／2=7×(7-1)／2=21条边，然后再添加一条边将第8个结点与G1连接起来，共需22条边。
    本题非常容易错误地选择选项A，主要原因是对“保证图G在任何情况下都是连通的”的理解，分析选项A，在图G中，具有8个顶点7条边并不能保证其一定是连通图，即有n-1条边的图不一定是连通图。
    分析选项D，图G有8个顶点28条边，那么图G一定是无向完全图，无向完全图能保证其在任何情况下都是连通的，但是这不符合题目中所需边数最少的要求。
转载请注明原文地址:https://kaotiyun.com/show/9ECi777K
本试题收录于： 计算机408题库学硕统考专业分类
0

计算机408

学硕统考专业

相关试题推荐
随机试题
最新回复(0)