若具有 (n) 个顶点的图是一个环，则它有（ ）棵生成树。
A. (n^2) B. (n) C. (n-1) D. 1
[tag_link]
正确答案：B
一个含 (n) 个顶点的环有 (n) 棵生成树。
环有 (n) 条边。删除环上的任意一条边，剩下的 (n-1) 条边都连接全部顶点且不再成环，恰好得到一棵生成树。可删除的边共有 (n) 条，故生成树数为 (n)。
生成树要求覆盖全部顶点且无环，不是任意删去一条边都要重新计数为 1；环上每一条边删除后都产生不同的生成树。