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

强连通图的性质不包括（ ）：

这题考的是强连通图与完全图的概念辨析。拿到题先别急着看选项，脑子里要把‘强连通’的定义刻清楚：有向图里任意两点间必须双向都有路径。然后逐项去套这个定义，看哪个选项描述的不是强连通而是别的概念，那个就是答案。

最容易栽跟头就是分不清‘强连通’和‘完全图’。强连通只要求两点之间能走通（可以拐弯、可以经过其他点），完全图才要求两点之间必须有直接连线。很多学生看到‘任意两点’就下意识想‘肯定有边’，或者把无向图的连通性套用到有向图上，觉得只要路通就行，忽略了强连通必须‘双向’都有路。另一个坑是把‘度数至少为 1'当成强连通的充分条件，其实度数够只是必要条件，不够强连通。

这道题考查的是图论基础中的强连通图、完全图以及连通性的概念辨析，属于 CSP 提高级常考的纯概念单选题。命题人特别喜欢挖这种‘看似都对，实则偷换概念’的坑，把强连通和完全图这两个容易混淆的定义放在一起，让你挑出‘不包括’的那一个。

首先，咱们得把强连通图的核心定义刻在脑子里：对于有向图，如果任意两个顶点 u 和 v 之间，既存在从 u 到 v 的路径，也存在从 v 到 u 的路径，那么这个图就是强连通的。注意关键词是‘路径’，不是‘边’，而且必须是‘双向’都有。

接下来咱们逐个选项掰开揉碎了看：

A 选项说‘每个顶点的度数至少为 1'。这其实是个必要条件。如果某个点度数是 0，那它既没有出边也没有入边，谁也去不了它，它也去不了谁，这图肯定不可能是强连通的。所以 A 是对的，强连通图里每个点度数确实至少为 1。

B 选项说‘任意两个顶点之间都有边相连’。停一下，这个描述太熟悉了，这是‘完全图’的定义啊！完全图要求每对顶点之间都有直接连线。但强连通图并不要求直接连线，它只要求能走通。举个例子，一个由三个点 A→B→C→A 构成的有向环，它是强连通的，但你不能说 A 和 C 之间有边相连，它们中间隔着 B。所以 B 这个性质不是强连通图必须具备的，它描述的是完全图，这就是本题要选的那个‘不包括’的选项。

C 选项说‘任意两个顶点之间都有路径相连’。这几乎就是强连通定义的另一种说法，只是没强调‘双向’。但在单选题里，结合上下文，这通常被理解为双向可达，或者至少是连通性的基础描述，它是强连通的必要条件，所以 C 是对的。

D 选项说‘每个顶点至少都连有一条边’。这和 A 选项其实是一回事，有向边算度数，所以 D 也是对的。

总结一下，A、C、D 都是强连通图必须具备的性质，只有 B 是把强连通偷换成了完全图，描述的是完全图的性质，而不是强连通的性质。所以答案选 B。

这类题的解题心法很简单：看到‘不包括’‘不属于’‘错误’这种否定式提问，千万别慌，先把核心概念的定义写出来（或者在脑子里过一遍），然后像筛子一样把每个选项往定义里套。哪个选项描述的不是这个概念，而是另一个相似概念，那个就是答案。命题人就是靠这种细微的概念偷换来拉开分差的。