NOIP 普及组初赛 · NOIP 2009 普及组初赛试题 第 18 题

已知 $n$ 个顶点的有向图，若该图是强连通的（从所有顶点都存在路径到达其他顶点），则该图中最少有多少条有向边？

这题考强连通图定义与最少边数，直接构造一个 n 个顶点的大环即可，每个点出度入度都为 1，且互相可达，边数恰好 n。

最容易把强连通和连通搞混，以为像无向图那样 n-1 条边就够了，其实有向图里 n-1 条边最多形成一棵有向树，根能到叶子但叶子回不去根，不满足双向可达；还有人会误选 n+1 以为多一条边更保险，其实 n 条已经够闭环了，再多就多余；完全图 n(n-1) 是最多情况，不是最少。

强连通图最少边数：一个环就够

n 个顶点的有向图，要是强连通，意味着从任意一个顶点出发，沿着有向边走，最终都能到达图中任意另一个顶点。换句话说，每对顶点之间都必须存在一条有向路径（双向都能走通）。

命题人怎么挖坑

很多学生看到“连通”就下意识想无向图：n 个点 n-1 条边就能连成一棵树。但这里有向边的方向性很关键——树形结构里，根到叶子有路，叶子回根却断了，显然不满足“互相可达”。命题人就是盯着这个认知盲区，让你把树形边数 n-1 错选成答案。

还有人会想“多一条边肯定更安全”，选 n+1，或者干脆觉得“完全图最稳”，选 n(n-1)。这些都是把“最少”理解成了“最保险”或“最密”。

思考心法：从哪入手？

拿到这种“最少边数”的图论题，第一反应应该是：能不能构造一个满足条件的极端情况，然后数它的边数？因为题目问的是下界，只要找到一个合法的图，它的边数就是候选答案，再证明没有更少的即可。

对于强连通，最“紧凑”的结构是什么？当然是让每个点都恰好有一条出边、一条入边，并且这些边连成一个圈。这样每个点都能沿着圈走到任何其他点——完美符合强连通定义，而且边数最少。

具体怎么算：构造大环

想象 n 个点排成一圈：

1→2→3→…→n→1

这就是一个长度为 n 的有向环。每个点 i 只有一条出边指向 i+1（n 指向 1），也正好有一条入边来自 i-1（1 的入边来自 n）。整个图里任意两点 u、v，从 u 出发沿着环走，迟早会经过 v；反过来从 v 走也能到 u。因此它是强连通的。

这个环用了多少条边？显然是 n 条。

为什么 n-1 不够？

假设只有 n-1 条边，根据握手定理，所有点的总出度之和等于总边数 n-1。但强连通要求每个点至少有一条出边（否则它永远出不去），所以每个点出度≥1，n 个点总出度至少是 n。矛盾！因此 n-1 条边不可能构成强连通图。

选项分析

• A: n ✅ 正好对应我们构造的大环，是最少边数。
• B: n+1 ❌ 不是最少，多一条边没必要。
• C: n-1 ❌ 有向树不满足双向可达，且出度总和不够。
• D: n(n-1) ❌ 这是完全有向图的边数，是最多情况，不是最少。

考频与趋势

“图的基本概念”在题库里共出现过 281 题，覆盖 11 个考试级别。其中“基础图论概念”子类（包含强连通这类定义辨析）共考过 8 题，分布在 2009-2021 年间，近年频率不高，但 2023 年后图论整体考频飙升（2023 年 36 题、2024 年 61 题、2025 年 58 题、2026 年 71 题），说明图论正在成为高频考点。

“强连通分量（SCC）”相关题目共 11 题，2009 年就有 1 题，2024-2026 年分别考了 2、5、1 题，显示强连通从基础概念逐渐向算法应用（如 Tarjan、Kosaraju）渗透。虽然本题是纯概念题，但结合近年趋势，未来可能更多出现在“给定图求 SCC 个数”或“判断是否存在强连通子图”这类综合题中。

预测

基于现有数据，强连通作为基础概念题已考过，但近年图论整体热度上升，且 SCC 应用题增多，可以合理预测：未来 2-3 年内，强连通图的最少边数这类概念题仍会偶有出现，但更多会转化为计算题或证明题（例如“证明 n 个顶点的强连通图至少 n 条边”或“给定 n 个点 m 条边，判断能否构成强连通图的最小 m”）。

暂无足够依据预测具体年份或题型变化，但建议考生：熟记强连通定义，掌握大环构造法，并警惕树形结构的陷阱——这题就是典型的概念陷阱题。

答案：A