🏷️ 知识点：环
课后题 年第 1 题
数据结构
选择题
一个有 n 个顶点和 n 条边的无向图一定是（ ）。
A. 连通的 B. 不连通的 C. 无环的 D. 有环的
[tag_link]
正确答案：D
结论
该图一定有环。
推导
无向森林若有 n 个顶点，边数至多为 n−1；当边数达到 n 时，不可能仍为森林，必含至少一个环。
易错点
n 条边不能推出连通；图可以分成多个连通分量，但边数超过森林上限仍必有环。
课后题 年第 13 题
数据结构
选择题
若具有 (n) 个顶点的图是一个环，则它有（ ）棵生成树。
A. (n^2) B. (n) C. (n-1) D. 1
[tag_link]
正确答案：B
结论
一个含 (n) 个顶点的环有 (n) 棵生成树。
推导
环有 (n) 条边。删除环上的任意一条边，剩下的 (n-1) 条边都连接全部顶点且不再成环，恰好得到一棵生成树。可删除的边共有 (n) 条，故生成树数为 (n)。
易错点
生成树要求覆盖全部顶点且无环，不是任意删去一条边都要重新计数为 1；环上每一条边删除后都产生不同的生成树。