NOIP 提高组初赛 · NOIP 2016 提高组初赛试题 第 8 题

$G$ 是一个非连通简单无向图，共有 $28$ 条边，则该图至少有（ ）个顶点。

拿到题先想：边数固定要顶点最少，得让边堆在一个连通分量里——把 28 条边凑成完全图 K₈，再补一个孤立点保证非连通，总和就是答案。

非连通图至少两个连通分量，容易漏掉那一个孤立点，直接算 K₈ 的 8 个点就选了 C；或者误以为可以拆成两个完全图，但那样顶点数只会更多。记住边数固定时，越集中越省点，集中到完全图是极致，剩下的点只能是孤立点，不能再连边。

考点概念：非连通图与完全图

非连通图意味着至少有两个连通分量。要让顶点数最少，就得让边尽可能‘挤’在一个分量里，剩下的分量只放孤立点（0 条边）。边数固定时，一个连通分量能容纳的最大边数出现在它是完全图的时候。

命题视角

命题人常在这里挖坑：一是让你忘记非连通至少两个分量，直接算连通图的最小顶点；二是让你把边拆成两个完全图，结果顶点数反而多了。这道题就是让你意识到：28 条边刚好凑成 K₈，再加一个孤立点就非连通了，顶点数就是 8+1=9。