NOIP 提高组初赛 · NOIP 2014 提高组初赛试题 第 13 题

设 $G$ 是有 $6$ 个结点的完全图，要得到一颗生成树，需要从 $G$ 中删去( )条边.

拿到题先算出完全图到底有几条边，再想想生成树必须几条边，一减就出来了。

很多同学习惯背公式 K_n 边数是 n(n-1)/2，但容易在代入数字时算错，比如把 6×5 算成 30 却忘了除以 2，或者把生成树边数记成 n，导致最后减出来是 5 或 11 这种奇怪答案。还有的同学会纠结生成树要删哪些边，其实只要是删够数量就行，不用管具体删哪条。

这道题考查的是完全图的边数计算和生成树的边数性质，属于图论基础概念，也是历年初赛最爱挖坑的地方。

命题人特别喜欢在计算环节设陷阱：比如故意把组合数公式写错，或者让你在算 6×5/2 时出错。生成树那边更是经典考点——n 个顶点的树一定有 n-1 条边，这个结论必须记牢。

拿到题先想什么？先算完全图 K₆ 有多少条边。6 个顶点两两连边，边数就是 C(6,2)=15 条。再想生成树：6 个顶点的树必须有 5 条边（n-1）。所以要从 15 条里删掉 15-5=10 条。

具体怎么算？

• 完全图边数：6×5÷2=15
• 生成树边数：6-1=5
• 需删除边数：15-5=10

避坑提醒：别把生成树边数当成 6，也别把完全图边数算成 30 或 12。还有，题目问的是“删去几条边”，不是“保留几条边”，方向别搞反。

考频与趋势：最小生成树相关题目在题库里共出现过 26 次，覆盖从普及组到提高组、GESP 五级到八级的所有级别。年份分布上，2025 年考得最多（10 题），2024 年有 5 题，2026 年也有 5 题，2015 年 2 题，其余年份各 1 题。分赛事看，GESP 八级占了 15 题，五级 4 题，NOIP 提高组初赛 2 题，NOIP 普及组初赛 2 题，CSP 提高级 1 题，七级 2 题。从数据看，这个知识点在 GESP 八级里高频出现，说明对概念掌握的考察越来越细致；同时近年 NOIP 提高组初赛也稳定出现，未来几年大概率还会继续考，尤其是结合具体图结构让你判断删边数量或构造生成树。

预测：基于现有数据，未来 NOIP 提高组初赛很可能继续以这种“完全图 + 生成树边数差”的形式出现，也可能换成“给定某图求最小生成树需删几条边”的变式，但核心还是考 n-1 这个性质。暂无足够依据预测更复杂的动态变化，因为目前所有题目都是静态图。