2. 考研
  3. 下列关于无向图的说法中，正确的是( )。 Ⅰ．无向图中某个顶点的度是指图中与该顶点连通的顶点数 Ⅱ．在一个具有n个顶点的无向图中，要连通全部顶点至少需要n-1条边 Ⅲ．无向图的邻接矩阵是对称矩阵 Ⅳ．具有n个顶点的无向图，最多有n个连通分量

下列关于无向图的说法中，正确的是( )。 Ⅰ．无向图中某个顶点的度是指图中与该顶点连通的顶点数 Ⅱ．在一个具有n个顶点的无向图中，要连通全部顶点至少需要n-1条边 Ⅲ．无向图的邻接矩阵是对称矩阵 Ⅳ．具有n个顶点的无向图，最多有n个连通分量

admin2019-05-10  32
问题 下列关于无向图的说法中，正确的是(    )。
Ⅰ．无向图中某个顶点的度是指图中与该顶点连通的顶点数
Ⅱ．在一个具有n个顶点的无向图中，要连通全部顶点至少需要n-1条边
Ⅲ．无向图的邻接矩阵是对称矩阵
Ⅳ．具有n个顶点的无向图，最多有n个连通分量
选项 A、仅Ⅰ、Ⅱ、Ⅲ
B、仅Ⅱ、Ⅲ、Ⅳ
C、仅Ⅲ
D、Ⅰ、Ⅱ、Ⅲ、Ⅳ
答案B
解析 Ⅰ：无向图顶点的度即为一个顶点所引出边的条数，等价于一个顶点所含有的邻接顶点的个数，而不是与该顶点连通的顶点数(这样就会扩大范围，如图6-6所示)，故Ⅰ错误。

    顶点V2的度应该是1，而如果度是按照图6-6中与该顶点连通的顶点数来定义，顶点V2的度应该是3，明显错误。
    Ⅱ：n个顶点的无向图要连通的话只需每个顶点做一个结点，构成一棵树即可(解题关键)，并且此时是边最少的情况。对于树来说，顶点的个数比边要多1，故Ⅱ正确。
    Ⅲ：显然，在无向图中，每条边(没有方向)对应于矩阵中与主对角线对称的两个“1”，因此无向图对应的邻接矩阵是对称的，故Ⅲ正确。
    Ⅳ：无向图的连通分量最少只有一个，即其自身；最多有n个，即该图没有边，则每个顶点构成一个连通分量，故Ⅳ正确。
转载请注明原文地址:https://jikaoti.com/ti/RHGjFFFM
本试题收录于： 计算机408题库学硕统考专业分类
0

计算机408

学硕统考专业

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