CSP-J 入门级 · CSP 2021 入门级第一轮 第 6 题

对于有 $n$ 个顶点、$m$ 条边的无向连通图 $(m>n)$，需要删掉（ ）条边才能使其成为一棵树。

这题别整那些复杂的并查集或缩点，直接盯着树的定义看。树是连通且无环的，n 个点几根边？死记硬背没用，推导一下：连通至少要 n-1 条，再多一条就成环了，所以 n 个点的树只能有 n-1 条边。原图 m 条，把 m 减去 n-1 就是答案。

学生最容易犯的错误是把树的边数记成 n 或者 n+1，导致算出 m-n 或者 m-n-1 这种选项。还有人会纠结‘删边会不会破坏连通性’，其实只要从连通图里删掉多余的边，剩下的 n-1 条边天然构成一棵树，连通性不会丢。另外，有些同学看到 m>n 就以为要删 m-n 条，忽略了树本身只有 n-1 条边这个核心约束。记住，删边的目的不是随便减，而是把边数强行压到 n-1，所以公式就是 m-(n-1)。

考点定位：图的基本概念——树与连通图。这道题本质是考你对‘树’的边数公式是否真正理解，而不是机械记忆。

概念拆解：

• 树：n 个顶点的树，必须满足两个条件：(1) 连通；(2) 无环。这两个条件合起来，直接推导出边数一定是 n-1。你可以这么想：从 n 个点开始，每加一条边如果保持连通且不形成环，就能多连一个点，一共连 n-1 次，边数就是 n-1。再加一条边，必然形成环，或者断开连通，都不符合树的定义。
• 连通图：题目给的是 m>n 的连通图，说明边数已经超过了树所需的最小值，多出来的边就是‘冗余’的，删了它们不会破坏连通性。

命题人挖坑视角： 命题人最喜欢在这里设陷阱，就是让你选 B (m-n) 或者 C (m-n-1)。为什么？因为很多同学脑子里只有‘删掉多余的边’，却忘了‘树到底需要多少边’。他们可能会想：‘连通图至少 n-1 条边，现在 m 条，删 m-(n-1) 条？’结果算错成 m-n。或者更离谱的，觉得删完要再减一条保证无环，变成 m-n-1。这些都是对‘树的结构’理解不透彻的表现。

思考心法与推导： 拿到题先别动笔算，先问自己：‘n 个点的树有几条边？’答案是 n-1。再问：‘现在我有 m 条边，要变成 n-1 条，得删几条？’很简单，m - (n-1)。展开就是 m - n + 1。这就是 D 选项。 验证一下：比如 n=3，树必须 3-1=2 条边。如果原图 m=4 条边（完全图 K4 去掉一条边就是 4 条），删 4-2=2 条，剩下 2 条，连通且无环，是树。公式成立。

避坑指南：

• 别把树的边数记成 n 或 n+1，这是最致命的。
• 别以为删边是为了‘凑整数’，删边是为了‘凑结构’，结构就是 n-1 条边。
• 别被 m>n 这个条件带偏，它只是告诉你有多余的边，不是让你算 m-n。

考频与趋势： 在题库的 281 道图论题里，‘图的基本概念’这一章考了 8 题，覆盖 2009-2021 年，属于低频考点，但恰恰是入门级的‘送分题’。历年分布：2020 年考了 4 题（那年入门级图论题扎堆），2021 年考了 1 题，正好就是这道题出现的年份。从数据看，这类纯概念辨析题在入门级考试中占比不高，但一旦出现，正确率往往两极分化，因为很多人卡在‘树边数’这个基础公式上。

预测： 基于现有数据，‘图的基本概念’在 2022-2026 年间几乎没有再考过（2022 年考了 3 题但都在其他章节，2023-2026 年该章节 0 题），说明命题组可能觉得这个点已经考透了，或者想换换花样。但图论是信息学竞赛的基石，尤其是树的结构，后续在动态规划、贪心、网络流等大题里都会反复用到。因此，虽然这种单选题短期内可能不再单独出现，但‘树的边数’这个知识点会以隐蔽的方式出现在压轴题的条件里（比如‘给定一棵树，问删掉几条边能变成森林’）。暂无足够依据预测未来会再次以纯概念单选题的形式出现，但建议学生务必把‘n 个点 n-1 条边’刻在脑子里，这是所有图论题的起点。