🏷️ 知识点：生成树计数

若具有 (n) 个顶点的图是一个环，则它有（ ）棵生成树。

A. (n^2) B. (n) C. (n-1) D. 1

[tag_link]

正确答案：B

结论

一个含 (n) 个顶点的环有 (n) 棵生成树。

推导

环有 (n) 条边。删除环上的任意一条边，剩下的 (n-1) 条边都连接全部顶点且不再成环，恰好得到一棵生成树。可删除的边共有 (n) 条，故生成树数为 (n)。

易错点

生成树要求覆盖全部顶点且无环，不是任意删去一条边都要重新计数为 1；环上每一条边删除后都产生不同的生成树。