CSP-S 提高级 · CSP 2021 提高级第一轮 第 7 题

$G$ 是一个非连通简单无向图（没有自环和重边），共有 $36$ 条边，则该图至少有（ ）个点。

这题核心就是利用非连通图至少有两个连通分量，把边塞进一个完全图，剩下的点只要凑够分量数就行。

最容易掉进的坑是忽略非连通条件，直接按连通图算，以为9个点就够了；或者误以为非连通图不能有边，把边数想多了；还有不少人算完全图边数时公式记混，把k(k-1)2写成k(k-1)36这种低级错误。

考点与概念

这道题考的是图的基本概念，特别是非连通图、完全图以及它们边数之间的关系。简单无向图意味着没有自环和重边，非连通则要求图中至少存在一对顶点无法互相到达，等价于图至少有两个连通分量。完全图$K_n$是$n$个顶点两两相连，边数固定为$n(n-1)/2$。

命题人视角

命题人喜欢在"最少顶点数"这类极值问题上挖坑。它想考察你是否真正理解"非连通"的含义：非连通并不禁止边存在，只是要求边不能把所有点都连在一起。为了求顶点最少，策略很明确：让一个连通分量尽可能"密"（容纳最多边），另一个分量尽可能"疏"（只占一个点）。这样总顶点数才会最小。