NOIP 提高组初赛 · NOIP 2017 提高组初赛试题 第 5 题

设 $G$ 是有 $n$ 个结点、$m$ 条边 $(n \leq m)$ 的连通图，必须删去 $G$ 的（ ）条边， 才能使得 $G$ 变成一棵树。

这题本质就是考树的边数性质。拿到题先想：n 个点的树一定只有 n-1 条边，这是铁律。既然原图 m 条边且连通，那多出来的边（也就是环）就是 m-(n-1)，直接算减法就行。

学生最容易把树的边数记成 n 条或者 n+1 条，导致算出 m-n 或 m-n-1 这种错误选项。另外，有些同学会纠结“删边后是否还连通”，其实题目已经保证原图连通，删掉多余的边（即构成环的边）只会把环断开，剩下的必然是连通的，这点不用额外验证。

考点概念：连通图删边成树

首先得把基本概念捋清楚：

• 连通图 G：n 个结点、m 条边（题目给的条件 n ≤ m）。连通意味着任意两点间都有路，但边多了就容易形成环。
• 树：n 个结点的树必须且只能有 n-1 条边。这是图论里最基础的结论，也是这题的命门。不管你怎么画，只要结点数是 n，边数少一个就是树；多一个就有环，少一个就不连通了。
• 生成树：连通图里包含所有 n 个结点的树，边数依然是 n-1。

命题视角：为什么考这个？

命题人喜欢在这种单选题里埋两个坑： 1. 数字陷阱：把 m-n 放在选项里，看着很像“总边减结点数”的直觉答案，但那是错的。因为树边数是 n-1，不是 n。 2. 逻辑陷阱：有些同学会想“删边会不会破坏连通性？”，其实题目已经限定原图连通，我们只需要删掉那些“多余”的边（即构成环的边），剩下的必然是连通的。命题人就是利用这种过度思考来迷惑人。