GESP 八级 · GESP 八级样题（C++ 组） 第 4 题

对于 4 个结点的简单有向图，最少（ ）条边可以形成一条覆盖所有顶点的环。

这题核心就是抓住“覆盖所有顶点”和“简单有向图”这两个限定词。拿到题先别看选项，脑子里画个 4 个点的圈，想想每个点要进一次出一次，边数自然就出来了。

最容易栽跟头的是忽略“简单图”这个条件，觉得能不能用重边凑数，或者把有向图当成无向图去算，那样边数会少。还有人会想当然以为少一条边也能绕一圈，其实 3 条边在 4 个点里根本连不成环，必然漏掉一个点。

【考点定位】图论基础中的哈密顿回路概念，以及简单有向图的度数性质。

【命题人视角】这道题看似考定义，实则考逻辑推导。命题人特意强调“简单有向图”，就是为了排除自环和多边，把边数死死钉在顶点数上；同时用“最少”二字，逼着你去想构造方案，而不是死记公式。如果不看清“简单”二字，很容易误选 C（3 条边），以为少一条也能绕，或者误选 A（5 条边），觉得多几条更保险。

【思考心法】拿到“覆盖所有顶点的环”这种描述，第一时间反应就是哈密顿回路。那哈密顿回路有什么硬性约束？在简单有向图中，每个顶点必须恰好有一条入边和一条出边，不能多也不能少。这意味着整个环的边数必然等于顶点数。对于 4 个顶点，那就是 4 条边。你可以试着画一下：1→2→3→4→1，刚好 4 条，每个点都进一次出一次，完美覆盖。如果你只有 3 条边，比如 1→2→3→1，那顶点 4 就彻底没戏了，既进不来也出不去，违背了“覆盖所有顶点”的前提。

【避坑指南】

• 别把“简单图”当废话：如果允许自环，4 个点确实可能用 3 条边凑出环（比如 1→2, 2→1, 1→1），但题干明确排除了这种情况。
• 别把“有向”当无向：无向哈密顿回路边数也是 n，但构造方式不同，容易混淆。
• 别被选项 A 带偏：5 条边在简单有向图里肯定不行，因为每个点只能有一条出边，4 个点最多 4 条出边，5 条边必然导致某个点出度为 2，那就不是环了，而是带分支的结构。

【考频与趋势】从题库数据看，图形结构考点在 GESP 八级中占比 73 题，其中图的基本概念更是高达 85 题，说明这类基础概念题是八级的重灾区。历年分布上，2024 年考了 61 题，2025 年 56 题，2026 年 40 题，呈现逐年递减但总量巨大的趋势，说明命题人不会轻易放弃这个考点，只是可能从纯概念转向更复杂的组合应用。

【预测】基于当前数据，未来 GESP 八级仍会高频出现图论基础题，但可能会结合更具体的应用场景（比如路径规划、网络流量等）来考察哈密顿回路或欧拉回路的概念。对于这类纯概念题，记住“简单有向哈密顿回路边数=顶点数”这个结论，基本就能稳拿分。暂无足够依据预测未来会突然变难或变易，保持对基础概念的敏感度即可。