CSP-J 入门级 · CSP 2020 入门级第一轮 第 8 题

有 $10$ 个顶点的无向图至少应该有（ ）条边才能确保是一个连通图。

这题考的是图论里连通图的最小边数，核心就是记住 n 个顶点的无向图连通最少要 n-1 条边（树），所以 10 个顶点直接减 1 就是答案。

最容易栽跟头的就是分不清连通图和完全图，完全图边数多到 n(n-1)/2，题目问的是‘至少’，肯定不能往多的方向想；还有会下意识把无向图当成有向图，以为要 n 条边才能强连通，其实无向图只要 n-1 条边连成树就通了。

考点定位：图的基本概念——连通图的最小边数。这是入门级高频送分点，只要公式记牢，几乎不会错。

概念拆解：

• 连通图：任意两个顶点之间至少有一条路径。换句话说，从图里随便拎两个点，你总能顺着边走到对方。
• 树：连通且无环的图。树有一个铁律：n 个顶点，恰好 n-1 条边。这是连通图的‘最小骨架’。
• 完全图：任意两点都有直接边相连。边数是 n(n-1)/2，这题肯定不是考这个，因为题目问的是‘至少’。

命题人怎么挖坑： 命题人喜欢把‘连通’和‘完全’混在一起考，或者故意不提‘无向’二字，让你往有向图想（有向图强连通最少 n 条边）。这道题虽然简单，但选项里放个 10 或 11，就是专门诱导你记错公式或者把无向当有向。

思考心法： 拿到题先想：n 个顶点要连通，最少几条边？ 1. 从 1 个点开始，加边才能连到第 2 个点，需要 1 条边。 2. 再加边连第 3 个点，又需要 1 条边。 3. …… 4. 连到第 n 个点，总共加了 n-1 条边。再加一条边就会形成环，不再是‘最少’了。 所以结论很稳：n-1 条边。

具体计算： 题目给的是 10 个顶点。 代入公式：10 - 1 = 9。 所以至少需要 9 条边。

避坑指南：

• 别把‘连通’和‘完全’搞混，完全图边数多到离谱，选那个肯定错。
• 别把无向图当成有向图，有向图强连通最少 n 条边，无向图只要 n-1 条边。
• 别被‘至少’这个词绕晕，‘至少’就是求最小值，直接想树形结构，别想多余边。

图形直观： 想象 10 个点排成一排，用 9 条线把它们串起来，这就是连通图的最小形态。少一条线，肯定断开了；多一条线，虽然还连通，但不是‘最少’。

考频与趋势： 从题库数据看，‘图的基本概念’一共考了 281 题，覆盖 11 个级别。其中‘基础图论概念’（含连通、树、完全图）专门考了 8 题，分布在 2009-2021 年，CSP 入门级占了 2 题。2023 年图论题突然暴增到 36 题，2024 年更是飙到 61 题，2025 年 58 题，2026 年 71 题，说明图论正在成为重头戏。虽然‘基础图论概念’这 8 题里 2020 年考了 4 题，但后续几年（2021-2026）几乎没再单独考过‘连通图最少边数’这种送分题，更多是结合路径、环或者算法题一起考。

预测： 基于现有数据，2027-2028 年图论题大概率还会继续增加，但像这种纯概念单选可能会减少，转而融入更复杂的图算法题中。暂无足够依据预测具体哪一年会再单独考这道题，建议把‘连通图最少边数=n-1’这个公式刻在脑子里，不管怎么变，这个底层逻辑不会变。