🏷️ 知识点：子图

共 2 道相关题目

课后题年第 3 题数据结构选择题

以下关于图的叙述中，正确的是（）。

A. 图与树的区别在于图的边数大于或等于顶点数 B. 假设图 G=(V,E)，V’⊆V、E’⊆E，则 V’ 和 E’ 构成 G 的子图 C. 无向图的连通分量是指无向图中的极大连通子图 D. 图的遍历就是从图中某一顶点出发访遍图中其余顶点

[tag_link]

正确答案：C

C 正确，连通分量就是极大连通子图。

A 错在树是特殊图，区别不由简单边数判定；B 还需每条所选边的端点均属于 V’；D 非连通图从一个顶点不能访问全部顶点。

“极大”表示不能再加入顶点而保持连通，不是“顶点数最多”的模糊表述。

课后题年第 4 题数据结构选择题

以下关于图的叙述中，正确的是（）。

A. 强连通有向图的任何顶点到其他所有顶点都有弧 B. 图的任意顶点的入度等于出度 C. 有向完全图一定是强连通有向图 D. 有向图的边集的子集和顶点集的子集都构成原有向图的子图

[tag_link]

正确答案：C

C 正确。

有向完全图对任意不同顶点都含相应方向的弧，因此任意顶点可达其他顶点，必强连通。A 把“存在路径”误作“直接有弧”；B 无一般性；D 子图中的边端点必须属于所选顶点集。

强连通要求路径可达，不要求每对顶点间都有一条直接弧；完全图才提供直接弧。