CSP-J 2022 第一轮 第 9 题：有向连通图邻接矩阵非零元素个数下界

题目

考虑由 $N$ 个顶点构成的有向连通图，采用邻接矩阵的数据结构表示时，该矩阵中至少存在（ ）个非零元素。

选项

• A. $N-1$
• B. $N$
• C. $N+1$
• D. $N^2$

答案

B

题解

答案：B．\(N\)。

按本题的默认含义，“有向连通图”指强连通图，即任意两个顶点之间都能沿有向路径互相到达。

当 \(N\ge 2\) 时，每个顶点至少要有一条出边，否则无法到达其他顶点。因此，图中至少有 \(N\) 条有向边。

这个下限可以达到：把所有顶点连成一个有向环： \[ v_1\to v_2\to\cdots\to v_N\to v_1。 \] 它恰好有 \(N\) 条边，且满足强连通。

邻接矩阵中，每条有向边对应一个非零元素，所以至少有 \(N\) 个非零元素。