NOIP 提高组初赛 · NOIP 2015 提高组初赛试题 第 9 题

$6$ 个顶点的连通图的最小生成树，其边数为（ ）。

这题其实是个送分陷阱，别被'最小生成树'这几个字绕晕了。核心只盯住一个性质：任何连通图的生成树，边数永远比顶点数少 1。拿到 6 个顶点，直接心算 6-1=5，答案 B 就出来了。

最容易栽跟头就是选 A 选项 6，把顶点数当成边数了，或者被'最小'二字干扰去纠结权值计算。其实生成树定义里就锁死了边数，跟权值大小无关。还有少数同学可能想当然觉得连通图边数可以更多，忘了生成树必须无环，多一条边就成环了，那就不是树了。

这道题考查的是图论中最小生成树（MST）的基本性质，属于基础概念辨析。虽然题目里出现了'最小生成树'，但陷阱在于它问的是'边数'，而不是'权值和'。很多初学者看到'最小'二字，下意识会想 Kruskal 或 Prim 算法，去比较边的权重，结果反而把自己绕进去了。命题人就是喜欢在这种纯概念题里挖坑，让你把简单问题复杂化。其实，生成树的核心定义就两句话：一是必须包含原图的所有顶点，二是必须连通且无环。对于任意一个包含 n 个顶点的连通图，其生成树的边数是一个定值——恰好是 n-1。这个结论不依赖于图的边权如何分配，也不依赖于具体用哪种算法求，是图论里的铁律。所以拿到这道题，正确的思考心法是：先剥离'最小'这个干扰词，回归到'生成树'的本质。题目给的是 6 个顶点的连通图，那它的生成树必然包含全部 6 个顶点，且边数必须是 6-1=5 条。如果边数多于 5，比如 6 条，根据图论定理，n 个顶点有 n 条边的连通图必然包含至少一个环，这就违背了'树'无环的定义；如果边数少于 5，比如 4 条，那 6 个顶点 4 条边不可能连通，违背了'树'连通的要求。因此，答案只能是 5，选 B。从历年考频看，生成树相关概念在初赛中出现频率极高。根据真实题库数据，'二叉树的遍历'这一关联考点（常与树结构一起考查）共考过 201 题，覆盖 2007 至 2026 年所有级别，其中 2024 年高达 58 题，2025 年 67 题，2026 年 28 题，2023 年 19 题，呈现明显的上升趋势，说明树结构及其衍生概念（如生成树、最小生成树）已成为近年命题的重中之重。分赛事来看，GESP 六级考了 100 题，七级 56 题，NOIP 提高组初赛 9 题，普及组 4 题，CSP 提高级 4 题。预测未来，随着数据结构在算法竞赛中地位的提升，生成树、并查集、最短路径等图论基础概念仍将是高频考点，尤其可能在选择题中继续以'概念辨析'或'简单计算'的形式出现，甚至结合动态规划或贪心算法出题。因此，这类基础概念题绝不能轻视，务必记住'生成树边数=n-1'这个黄金公式，避免在简单问题上丢分。