CSP-S 提高级 · CSP 2019 提高级第一轮 第 8 题

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

这题核心就是抓“非连通”四个字。既然要顶点最少，那有边的部分必须尽可能稠密，直接凑成完全图；剩下的顶点只能孤立。算出能装下28条边的完全图顶点数，再加一个孤立点，答案就出来了。

最容易掉进的坑就是忽略“非连通”这个限定条件，顺手把图当成连通的去算，那样8个顶点就够了，直接选D就错了。还有同学可能会纠结能不能拆成两个都有边的连通分量来省顶点，其实边数固定的情况下，拆成两个分量只会让需要的总顶点数变多，不如让一个分量吃光所有边、另一个分量只留一个孤立点来得省。另外计算完全图边数公式时，别把n(n-1)/2记成n(n-1)，那样会算出n=11，明显不对。最后别忘了孤立点也要计入总顶点数，这是很多学生失分的地方。

这道题考什么

考的是图的基本概念：连通性、完全图的边数公式，以及如何在“非连通”的约束下构造顶点数最少的图。

概念人话版

完全图就是n个点之间两两都有边，边数公式是 E = n(n-1)/2。比如K5有10条边，K8有28条边，这个公式必须熟。 连通图意味着任意两点都有路可达；非连通图则至少有一对点没路，换句话说，图里至少得有两个独立的“块”（连通分量）。