🏷️ 知识点：极小连通子图

设 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 条边，因此无环，并且删除任意一条边都会失去连通性，所以是极小连通子图。连通分量则是原图中的极大连通子图；生成树不要求包含该分量的全部边，故不一定是连通分量。

易错点

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