🏷️ 知识点：边数与树数

若一个具有 (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)。

易错点

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