模拟卷 数据结构 图的概念 选择题
第 7 题

以下关于图的表述中,正确的是( )。

A. 强连通有向图的任何顶点到其他所有顶点都有弧 B. 图与树的区别在于图的边数大于或等于顶点数 C. 无向图的连通分量指无向图中的极大连通子图 D. 假设有图 ,顶点集 ,则 构成 的子图。

图的概念

[tag_link]

正确答案:C

首先分析选项 A:强连通有向图要求任意两个顶点之间存在双向路径,但并不要求直接有弧(即直接的边)。

例如,一个包含三个顶点的有向环,顶点间通过路径相连而非都有直接弧,因此该表述错误。

接着看选项 B:图与树的区别在于树是无环连通图,且对于 n 个顶点的树,边数为 n-1。 图的边数可以小于、等于或大于顶点数,例如孤立顶点图边数少于顶点数,因此该表述不准确。

选项 C 正确,因为无向图的连通分量定义为极大连通子图,即不能再添加其他顶点和边而保持连通的子图,这是图论中的标准概念。

最后检查选项 D:子图需要顶点集 V’⊆V 和边集 E’⊆E,且 E’中边的端点必须都在 V’中。 选项仅说明 V’和 E’是子集,未强调边的端点限制,因此表述不完整,错误。

综上,正确选项为 C。