🏷️ 知识点：连通分量

共 4 道相关题目

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

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

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

[tag_link]

正确答案：C

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

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

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

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

设 G=(V,E)，G’=(V’,E’) 是 G 的一棵生成树。下列说法中错误的是（）。

I. G’ 是 G 的连通分量 II. G’ 是 G 的无环子图 III. G’ 是 G 的极小连通子图，且 V’=V

A. I、II B. 仅 III C. II、III D. 仅 I

[tag_link]

正确答案：D

错误的只有 I，答案为 D。

生成树覆盖原图全部顶点（V’=V），是连通子图且含 n−1 条边，因此无环，并且删除任意一条边都会失去连通性，所以是极小连通子图。连通分量则是原图中的极大连通子图；生成树不要求包含该分量的全部边，故不一定是连通分量。

“极小”与“极大”相反：生成树按边数是极小连通子图，连通分量按包含关系是极大连通子图，不能混淆。

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

具有 51 个顶点和 21 条边的无向图的连通分量最多为（）。

A. 33 B. 34 C. 45 D. 32

[tag_link]

正确答案：C

最多有 45 个连通分量。

要让连通分量尽可能多，应把边集中在尽量少的顶点上。21 条边可由完全图 (K_7) 提供，因为 (\binom{7}{2}=21)。其余 44 个顶点均孤立，因此连通分量数为 (1+44=45)。

不要把 21 条边简单地当作 21 个分量；一条边会把两个顶点合并到同一个连通分量。极值构造应优先使用边数恰好足够的完全图，再保留孤立点。

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

若一个具有 (n) 个顶点、(e) 条边的无向图是一个森林，则该森林中必有（）棵树。

A. (n) B. (e) C. (n-e) D. 1

[tag_link]

正确答案：C

森林中树的棵数为 (n-e)。

森林的每个连通分量都是一棵树。若共有 (c) 棵树，第 (i) 棵树有 (n_i) 个顶点和 (n_i-1) 条边，则总边数 (e=\sum(n_i-1)=n-c)。因此 (c=n-e)。

只有在无环的森林中才能直接使用“边数 = 顶点数 − 树的棵数”；含环图不满足每个连通分量都是树。