CSP-S 2024 第一轮 第15题：如图是一张包含7个顶点的有向图。如果要删除其中一些边，使得从节点1到节点7没

题目

如图是一张包含 $7$ 个顶点的有向图，如果要删除其中一些边，使得从节点 $1$ 到节点 $7$ 没有可行路径，且删除的边数最少，请问总共有多少种可行的删除边的集合？（ ）

选项

• A. 1
• B. 2
• C. 3
• D. 4

答案

D

题解

选 D，4 种。

先确定最少要删几条边。图中有两条没有公共边的路径：

• \(1\to2\to5\to7\)
• \(1\to4\to6\to7\)

因此，删一条边不可能同时截断它们，至少要删 2 条边。而删掉 \(5\to7\) 和 \(6\to7\) 就能满足要求，所以最少恰好是 2 条。

接下来分类计数：

① 删掉 \(4\to6\)。 此时从 1 到 7 只剩路径 \(1\to2\to5\to7\)，第二条边可以从这条路径中任选一条，共 3 种： \[ \{4\to6,\ 1\to2\},\quad \{4\to6,\ 2\to5\},\quad \{4\to6,\ 5\to7\}. \]

② 不删 \(4\to6\)。 从 1 到 4 有三条没有公共边的路径： \[ 1\to4,\qquad1\to2\to4,\qquad1\to3\to4. \] 只删两条边，节点 4 必然仍可达，因此节点 6 也可达，必须删掉 \(6\to7\)。

剩下的一条边还要同时截断 \(1\to2\to5\to7\) 和 \(1\to\cdots\to6\to5\to7\)，只能删 \(5\to7\)。共 1 种。

所以总数为 \(\boxed{3+1=4}\)。