CSP-S 2026 第一轮 第 8 题：有向无环图 G 顶点集为 1,2,3,4

题目

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

选项

• A. 12
• B. 8
• C. 4
• D. 6

答案

B

题解

选 B，8 种。

边 \(1\to2\)、\(1\to3\) 要求：1 必须排在 2 和 3 前面，而 2、3 的先后顺序不限。

先不考虑顶点 4，只有两种拓扑序：

• \(1,2,3\)
• \(1,3,2\)

顶点 4 没有任何连边，可以插入每种序列的 4 个位置（开头、两个间隙、末尾）。

因此共有： \[ 2\times4=\boxed{8}\text{ 种。} \]