单选题 下列关于无向图的说法中,正确的是______。
Ⅰ.无向图中某个顶点的度是指图中与该顶点连通的项点数
Ⅱ.在一个具有n个顶点的无向图中,要连通全部顶点至少需要n-1条边
Ⅲ.无向图的邻接矩阵是对称矩阵
Ⅳ.具有n个顶点的无向图,最多有n个连通分量
  • A.仅Ⅰ、Ⅱ、Ⅲ
  • B.仅Ⅱ、Ⅲ、Ⅳ
  • C.仅Ⅲ
  • D.Ⅰ、Ⅱ、Ⅲ、Ⅳ
【正确答案】 B
【答案解析】[解析] Ⅰ:无向图顶点的度即为一个顶点所引出边的条数,等价于一个顶点所含有的邻接顶点的个数,而不是与该顶点连通的顶点数(这样就会扩大范围,如图所示),故Ⅰ错误。
[*]
顶点V2的度应该是1,而如果度是按照图中与该顶点连通的顶点数来定义,顶点V2的度应该是3,明显错误。
Ⅱ:n个顶点的无向图要连通的话只需每个顶点做一个结点,构成一棵树即可(解题关键),并且此时是边最少的情况。对于树来说,顶点的个数比边要多1,故Ⅱ正确。
Ⅲ:显然,在无向图中,每条边(没有方向)对应于矩阵中与主对角线对称的两个“1”,因此无向图对应的邻接矩阵是对称的,故Ⅲ确。
Ⅳ:无向图的连通分量最少只有一个,即其自身;最多有n个,即该图没有边,则每个顶点构成一个连通分量,故Ⅳ正确。