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

欧拉图 $G$ 是指可以构成一个闭回路的图，且图 $G$ 的每一条边恰好在这个闭回路上出现一次（即一笔画成）。在以下各个描述中，不一定是欧拉图的是（ ）。

拿到题先别急着套公式，盯着选项 D 里的关键词“每个顶点恰好一次”看，这其实是哈密顿回路，跟欧拉图关注的“每条边恰好一次”完全是两码事，这就是出题人挖的坑。

很多同学容易把欧拉图和哈密顿图的概念记混，看到“恰好一次”就慌了，以为是在考欧拉定理。其实欧拉图的核心是边，只要所有顶点度数都是偶数，就能一笔画成闭回路；而 D 选项描述的是经过所有顶点，哪怕图里有很多重复的边，只要顶点都跑到了就算满足条件，这跟能不能一笔画完边没关系。还有的同学会纠结 E 选项，觉得“闭迹”听起来像路径，其实闭迹本身就是欧拉环游的另一种说法，只要它是闭的且覆盖所有边，那就一定是欧拉图。

这道题考查的是图论中欧拉图与哈密顿图的概念辨析，核心在于区分“边”和“顶点”两个不同的遍历对象。

概念人话版：

• 欧拉图：能不能一笔画完，而且必须回到起点。数学上等价于“图里所有顶点的度数（连接的边数）都是偶数”。
• 哈密顿图：能不能走一遍，把图里所有点都踩一遍，且不能重复踩。这跟边没关系，只跟点的排列有关。

命题人怎么挖坑： 题目把“欧拉环游”“欧拉闭迹”这些专业术语都列出来了，看起来像是在考定义，其实是在考你认不认识 D 选项那个“存在一条回路，通过每个顶点恰好一次”到底在说什么。命题人故意把哈密顿回路（点遍历）伪装成欧拉图的描述，利用大家容易混淆“边”和“点”的心理，让你掉进陷阱。记住，欧拉看边，哈密顿看点，这是铁律。

拿到题怎么想：

• 先看 A：没有度为奇数的顶点 → 所有点度数都是偶数 → 满足欧拉定理 → 是欧拉图。
• 再看 B：包含欧拉环游 → 环游本身就是覆盖所有边且闭合 → 当然是欧拉图。
• C：包含欧拉闭迹 → 闭迹就是欧拉环游的另一种说法 → 也是欧拉图。
• E：本身为闭迹 → 闭迹覆盖所有边且闭合 → 是欧拉图。
• 最后看 D：存在一条回路，通过每个顶点恰好一次 → 这是在说哈密顿回路！哈密顿回路只保证每个点被访问一次，完全不关心边是否重复或者是否覆盖所有边。比如一个三角形加一条从顶点连到自身的重边，所有点都能走一遍（哈密顿），但那条重边没法一笔画进去再出来（度数变了），所以它不是欧拉图。因此 D 不一定是欧拉图。

易错点提醒： 千万别看到“恰好一次”就以为是欧拉定理的“度数偶数”条件。欧拉定理说的是“度数”恰好是偶数，而不是“顶点”恰好出现一次。这两个“恰好一次”长得像，但意思天差地别。还有，有些同学会纠结 E 选项，觉得“闭迹”是不是只覆盖部分边？其实闭迹的定义就是覆盖所有边且闭合，所以 E 一定是欧拉图。

考频与趋势： 从题库数据看，“图的基本概念”在 281 道题里出现过，覆盖 11 个级别。历年分布比较均匀，2007 到 2019 年每年 1-3 题不等，2020 年后明显升温，2023 年突然跳到 36 题，2024 年 61 题，2025 年 58 题，2026 年更是达到 71 题，说明图论概念题在近年考试中的比重越来越大，尤其是初赛阶段。分赛事来看，GESP 八级和七级各 85 题，占比最高，其次是五级 36 题、六级 27 题，NOIP 提高组初赛也有 10 题。这说明无论是等级考试还是信息学竞赛，图论基础都是高频考点。

未来预测： 基于 2023-2026 年数据，图论概念题的考频呈指数级上升趋势，尤其是哈密顿与欧拉图的辨析、最短路径算法基础等，未来几年仍将是初赛和 GESP 高分段的重灾区。命题人可能会继续用“恰好一次”这种模糊表述来挖坑，或者把欧拉图与哈密顿图混合在同一个情境题里，要求判断某个具体图是否同时满足两个条件。暂无足够依据预测具体的题目形式，但可以肯定的是，只要你还分不清欧拉和哈密顿，将来大概率还会在这类题上丢分。

正确答案：D