GESP 八级 · GESP 202312 C++ 八级 第 6 题

一个无向图包含 $n$ 个顶点，则其最小生成树包含多少条边？（ ）。

拿到题先别急着背公式，先圈出题干里有没有‘连通’二字。无向图未必连通，只有连通图才存在最小生成树，所以第一步是判断存在性，而不是直接算边数。

绝大多数同学看到‘最小生成树’就条件反射选 n-1，完全忽略了前提条件。其实最小生成树定义里明确要求‘包含所有顶点’，如果图不连通，连所有顶点都做不到，自然不存在最小生成树。命题人就是利用大家记结论不验条件的惯性挖坑，让你掉进 A 选项的陷阱里。

【考点定位】 GESP 八级图论模块，核心考查‘最小生成树的存在性条件’。命题人特意在题干中省略了‘连通’二字，就是想测试你审题的严谨性——绝大多数人看到‘最小生成树’就机械套用‘n-1 条边’，却忘了它必须建立在图连通的前提下。

【概念拆解】 先说清楚什么叫最小生成树：它是连通无向图中权值最小的生成树，必须满足两个硬性条件：一是包含所有 n 个顶点，二是构成一棵树（因此恰好有 n-1 条边）。如果图本身不连通，顶点就被分割成了若干个独立的连通分量，你想取一棵树覆盖所有点，根本做不到。这时候存在的只能是‘生成森林’——每个连通分量里各取一棵最小生成树，但整体不是一棵树，所以严格意义上‘最小生成树不存在’。

【命题视角】 题目只问‘包含多少条边’，看似在考公式，实则是在考逻辑判断。命题人把 A 项设为 n-1，就是利用大家‘背公式不验条件’的思维惯性；D 项‘可能不存在’才是唯一严谨的答案。这属于典型的‘语义陷阱’：题干缺一个词，结论就全变了。

【思考心法】 拿到这类题，脑子里要先过一遍流程：第一步，看图是否连通？不连通直接排除所有具体边数选项，选 D；第二步，若连通，再想边数是多少？树的基本性质决定了 n 个点必有 n-1 条边，所以选 A。千万别一上来就套公式，得先确认对象存在。

【避坑指南】 最容易掉进的坑就是 A 项。很多同学看到‘最小生成树’就条件反射选 n-1，完全忽略了前提。其实最小生成树定义里明确要求‘包含所有顶点’，如果图不连通，连所有顶点都做不到，自然不存在最小生成树。命题人就是利用大家记结论不验条件的惯性挖坑，让你掉进 A 选项的陷阱里。阴险细节在于题干刻意省略‘连通’二字，属于语义陷阱。

【考频与趋势】 从历年真题看，‘图连通性判断’在 2023 年考了 32 题，2024 年更是达到 61 题，2025 年 56 题，2026 年 40 题，属于高频考点。而‘最小生成树’专题虽然总数不多（26 题），但在 2025 年考了 10 题，2026 年考了 5 题，说明命题人正在逐步加大对该知识点的考查力度，尤其是结合连通性判断的综合题。

【预测】 基于数据趋势，未来 GESP 八级甚至七级考试中，仍会高频出现‘先判断连通性，再求边数’这类题型，命题人可能会把‘连通图’改成‘可能不连通图’，或者把‘最小生成树’换成‘生成森林’来进一步区分层次。只要图论基础打牢，这类题就是送分题；若只背结论，必踩坑。