CSP-S 提高级 · CSP 2022 提高级第一轮 第 9 题

每个顶点度数均为 2 的无向图称为“2 正规图”。由编号为从 1 到 n 的顶点构成的所有 2 正规图，其中包含欧拉回路的不同 2 正规图的数量为（ ）。

这题本质是圆排列计数。2 正规图必由若干环组成，欧拉回路条件强制图连通，即只有一个大环。把 n 个点围成环，先除以旋转同构 n 得 (n-1)!，再考虑环可翻转（镜像对称）同构，最终除以 2，答案即 (n-1)!/2。

学生最容易栽在两个坑：一是把圆排列当成直线排列，直接选 n!，忘了圆环旋转后起点变化不算新图；二是只除以旋转同构得到 (n-1)!，却漏了翻转同构，因为无向图的环顺时针 A-B-C 和逆时针 A-C-B 在几何上是同一个图，题目默认这种镜像视为相同，所以必须再除以 2。还有个隐蔽坑是看到“包含欧拉回路”就以为要验证度数或连通性，其实对 2 正规图来说，只要图连通（一个大环）就自动满足欧拉回路条件，这个条件纯粹是用来锁定“一个大环”而非“多个小环”的计数模型。

考点定位：图论基础（2 正规图的结构特征）+ 组合数学（圆排列与同构计数）。题目问的是“不同 2 正规图的数量”，核心在于理解“不同”的定义——在无向图中，两个图若可通过旋转或翻转重合，则视为同一个图。

概念拆解： 1. 2 正规图：每个顶点度数均为 2。在无向图中，度数为 2 意味着每个点恰好连着两条边。这样的结构只能是若干个环（cycle）的并集。想象一下，从任意点出发，沿着边走，因为度数固定为 2，你一定会绕一圈回到起点，形成一个小环；如果还有其他点没被访问到，就会形成另一个独立的环。 2. 欧拉回路：存在欧拉回路的充要条件是图连通且所有顶点度数为偶数。本题中所有点度数已是 2（偶数），所以“包含欧拉回路”这个条件等价于要求图是连通的。既然图必须连通，就不能有多个小环，只能是一个包含所有 n 个顶点的大环。

命题人视角： 命题人故意抛出“包含欧拉回路”这个条件，不是为了让你去验证度数或跑 DFS 找回路，而是为了把计数模型从“若干个环的并集”锁定为“恰好一个大环”。如果去掉这个条件，题目就会变成求所有 2 正规图（即所有环划分方案）的数量，那就要用斯特林数或贝尔数了，难度陡增。这里它只是帮你做减法：从所有环组合中剔除不连通的情况，只留一个环。

思考心法与计算： 拿到题，先画图想结构 → 确定是单一大环 → 转化为 n 个点围成圆环的排列数。

• 线性排列：n 个点排成一排有 n! 种。
• 圆排列（旋转同构）：圆环可以旋转，起点不同但相对顺序相同的算同一个环。例如 n=3 时，(1,2,3) 旋转后变成 (2,3,1) 或 (3,1,2)，本质一样。因此要除以 n，得到 (n-1)!。
• 翻转同构（镜像对称）：无向图没有方向，顺时针序列 (1,2,3) 和逆时针序列 (1,3,2) 在几何上是同一个环（就像圆桌可以翻面看）。所以还要再除以 2。

综上，不同的大环数量为 (n-1)! / 2。

避坑指南：

• 别选 n!：那是直线排列，没考虑旋转。
• 别选 (n-1)!：漏了翻转，把镜像当成两个图了。
• 别选 n!/2：旋转除的是 n 不是 1，数学上 n!/2 = n × (n-1)! / 2，多乘了个 n，完全不对。
• 别纠结“欧拉回路”的具体验证：对 2 正规图，连通即满足，无需额外计算。

考频与趋势：

• 图基本概念在题库中非常活跃，共 281 题，尤其在近年爆发式增长：2023 年 36 题、2024 年 61 题、2025 年 58 题、2026 年 71 题，说明图论是 CSP 提高级乃至更高阶考试的必考内容。
• 排列组合基础也高频出现，147 题，2024 年 40 题、2025 年 43 题，组合计数是近年热点。
• 欧拉路径/回路本身考得少，仅 3 题（2022、2024、2026 各 1 题），且都集中在 CSP 提高级和 GESP 八级。但结合本题可见，命题人正将欧拉回路作为“连通性约束”的包装，与圆排列结合出题。

预测： 基于 2024-2026 年图论与排列组合双高发的趋势，以及欧拉回路近年零星但精准出现的规律，未来（2027-2028）极有可能继续以“图结构 + 同构计数”的形式考查，例如问“n 个顶点的 3 正规连通图有多少种”或“带标号的多边形旋转翻转同构数”。这类题目会要求考生先识别图的拓扑特征，再转化为经典的圆排列、项链排列等组合模型，最后处理旋转/翻转同构。暂无足够依据预测具体年份或题型细节，但“图结构识别 + 组合计数 + 同构除数”的组合模式大概率延续。