CSP-S 2022 第一轮 第8题：强连通图的性质不包括（)：

题目

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

选项

• A. 每个顶点的度数至少为 1
• B. 任意两个顶点之间都有边相连
• C. 任意两个顶点之间都有路径相连
• D. 每个顶点至少都连有一条边

答案

B

题解

答案是 B。

强连通图是指：在有向图中，任意两个不同的顶点 \(u,v\)，都存在从 \(u\) 到 \(v\) 的路径，也存在从 \(v\) 到 \(u\) 的路径。路径可以经过其他顶点，不要求两点之间直接有边。

例如，有向环 \(1\to2\to3\to4\to1\) 是强连通图，但顶点 1 和 3 之间没有直接相连的边，因此 B 不一定成立。

在通常默认至少有两个顶点的情况下，A、D 都成立；C 就是强连通的核心性质。