CSP-S 提高级 · CSP 2026 提高级第一轮 第 8 题

【单选】有向无环图 G 顶点集为 {1, 2, 3, 4}，边集为 {(1, 2), (1, 3)}，顶点 4 与任何顶点均不相邻。该图不同的拓扑序共有多少种（ ）。

顶点 4 与谁都不相邻，位置完全自由；剩下 3 个顶点只需满足"1 在 2、3 之前"。用排列计数：总排列 4! = 24，而 {1,2,3} 中 1 排最前的概率是 1/3，故为 8。

忘记顶点 4 可以插在任意位置（得到 2! = 2 或 4 之类的错值）；或者把"1 在 2、3 之前"误当成"1 必须紧邻 2、3"。

解析

本题考查拓扑排序的计数。

图的结构

• 顶点集 {1, 2, 3, 4}
• 边集 {(1,2), (1,3)} → 约束：1 必须排在 2 之前，1 必须排在 3 之前（2 与 3 之间无约束）
• 顶点 4 与任何顶点均不相邻 → 4 的位置完全自由

方法一：排列计数

4 个顶点共有 4! = 24 种排列。在 1、2、3 的相对顺序中，"1 排在这三者最前"恰好占 1/3（因为 1、2、3 的相对次序完全均等）。因此合法拓扑序数：

24 × 1/3 = 8

方法二：逐个枚举（互相印证）

先排 1、2、3 的满足约束的相对顺序：1 在最前，2、3 随意 → 2 种（1,2,3 与 1,3,2）。 再把 4 插入到 3 个顶点的序列中，共 4 个位置可选：

• (1,2,3)：4 可插在 4 个位置 → 4 种
• (1,3,2)：同样 4 种

合计 2 × 4 = 8 种 ✓

其他选项为什么错

• C. 4：把 4 漏掉（只数了 4 的位置自由度而没乘 2 种内部顺序，或只算 2 种内部顺序乘 2）；
• A. 12、D. 6：把 2、3 之间也当成有约束，或把 1 与 2、3 的约束算成了"1 紧邻紧跟"。

记忆点

• 孤立点/无约束点可以最后插入计数：先排受约束的部分，再把自由点插入空位（插入位置数 = 已排元素数 + 1）；
• 拓扑序的必要条件：图中所有边都从前指向后；孤立顶点个数为 k 时往往带来 k! 量级的自由度。