CSP 模拟 · CSP 2020 第一轮（初赛）模拟 第 14 题

一个 $7$ 个顶点的完全图需要至少删掉多少条边才能变为森林？

这题考图论里“森林”和“完全图”的基本概念，核心是记住：n 个顶点的森林最多有 n - 1 条边。完全图边数是 n(n-1)/2，用这个公式直接算差值就行，别去画图画图。

最容易把森林当成“连通图”或“树”，以为删边要保留连通性，结果多删了好几条；也有人把完全图边数记成 n(n+1)/2 或者 n²，把 n=7 代进去算出 21 或 49，然后随便选个接近的选项。还有同学会纠结“删哪条边”，其实题目只问数量，不需要具体方案。

这道题考查图论中“森林”和“完全图”的基本概念，以及简单的计数计算。

首先明确概念：图由顶点和边构成。森林是“无环图”的集合，相当于若干棵树的并；题目要求“变为森林”，意味着最终图里不能有任何环。对于 n 个顶点的森林，边数最多是多少？每棵树最多有 (顶点数 -1) 条边，所有树加起来就是 n - 树的数量。要让边数尽可能多，就要让树的数量尽可能少，最少是 1 棵树，所以 n 个顶点的森林最多有 n - 1 条边。

接下来看完全图：n 个顶点两两之间都有边，总边数是组合数 C(n,2) = n(n-1)/2。本题 n=7，代入得 7×6/2 = 21 条边。

现在要问：从 21 条边删掉多少条，才能让图变成森林？只要保留最多的边（即森林允许的最大边数）即可，保留 n-1 = 6 条，删掉的边数就是 21 - 6 = 15。

命题人为什么这么考？因为完全图边数公式和森林最大边数这两个基础结论，学生往往背得熟练，但一遇到“需要删多少边”这种逆向表述，就容易掉进陷阱：要么误以为要保留连通性（多删），要么把森林当成树（只保留一棵），要么把完全图边数记错。所以题目特意用“至少删掉多少条”来逼你抓住“保留最多边”这个关键点。

思考心法：拿到题先看目标状态——森林。问“至少删多少”，等价于“最多能保留多少”。保留多少？森林最多 n-1 条边。再算原来有多少边？完全图 n(n-1)/2。两者相减就是答案。不需要画图，不需要枚举删边方案，纯代数计算。

避坑指南：别把森林当成“连通图”；别把森林当成“一棵树”；别把完全图边数记成 n² 或 n(n+1)/2；别被“删掉哪条边”这种细节带偏，题目只问数量。

考频与趋势：在近年 CSP-J/S 与 GESP 的图论选择题中，完全图边数公式和森林/树的边数关系是高频考点，几乎每年都有变形出现（如“最少加多少边”“最多删多少边”等）。本题属于最基础的直接计算型，难度不大，但容易因概念混淆丢分。

预测：未来仍会考类似“完全图变森林/树”的逆向计数，可能增加一点干扰项，比如给一个非完全图让你算删边数，或者把顶点数改成 8、9 让你快速心算。暂无足够依据预测更复杂的变形，建议先把 n(n-1)/2 和 n-1 这两个公式练到肌肉记忆。