CSP-S 2022 第一轮 第9题：每个顶点度数均为2的无向图称为“2正规图”。由编号为从1到n的顶点构成的所有2正

题目

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

选项

• A. n!
• B. (n-1)!
• C. n!/2
• D. (n-1)!/2

答案

D

题解

选 D．\(\dfrac{(n-1)!}{2}\)（默认 \(n\ge 3\)，且为简单无向图）。

每个顶点度数都是 2，因此 2 正规图由若干个互不相交的环组成。要存在欧拉回路，就必须连通，所以这个图只能是一个包含全部 \(n\) 个顶点的大环。

接下来数不同的大环：

1. 固定顶点 1 为起点，其余 \(n-1\) 个顶点按顺序排列，共有 \((n-1)!\) 种。
2. 因为是无向图，顺时针和逆时针得到的是同一个环。例如 \(1\to2\to3\to4\to1\) 与 \(1\to4\to3\to2\to1\) 相同，所以再除以 2。

因此答案为 \[ \boxed{\frac{(n-1)!}{2}}. \]