NOIP 普及组初赛 · NOIP 2017 普及组初赛试题 第 10 题

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

这题考树的基本性质。拿到题先想：树必须连通且无环，n个结点的树边数固定是n-1。题目给的图有m条边，只要把多余的删掉就行，直接算m-(n-1)就能选出答案。

很多同学会死记硬背公式，或者被选项D的n-m+1这种‘符号反了’的陷阱带偏。其实核心就两点：一是树的边数永远是n-1，不是n；二是题目特意给了n≤m，就是为了告诉你图是连通的，否则没法保证删边后还能连通。如果图不连通，删边只会更散，所以这个条件就是提示你‘连通图变树’的模型。

考点与概念

这道题考查的是图论中最基础的树的定义：一个有n个结点的树，必须满足两个条件——连通且无环。而这两个条件合起来，直接推导出一个铁律：n个结点的树，边数恰好是n-1。这是所有树形结构（包括二叉树、森林等）的通用公式，也是后续很多算法（如最小生成树、拓扑排序）的基石。

题目给出的图G有n个结点、m条边，且明确说了n≤m。这个条件非常关键：它保证了图是连通的（因为n个结点连通至少需要n-1条边，这里m≥n>n-1，所以肯定连通）。既然连通，那它内部一定存在环，否则边数不可能这么多。

命题人的挖坑视角

命题人为什么选这个题？因为它看似简单，实则有三个经典坑点：

1. 树的边数记错：很多初学者会误以为树有n条边，或者把n和n-1搞混。选项B就是m-n，少算了一条，就是冲着这个坑来的。 2. 符号反了：选项D是n-m+1，把m和n的位置颠倒，看起来很像正确答案，其实是完全反了。 3. 忽略连通前提：如果图不连通，删边只会让它更散，无法变成树。题目特意强调n≤m，就是在提示‘这是一个连通图，删边后还能保持连通’，所以直接套用公式即可。