GESP 七级 · GESP 202312 C++ 七级 第 5 题

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

这题核心就一个词：非连通。想顶点最少，就得让一个连通块拼命吃边（完全图最省顶点），另一个连通块只剩1个孤立点。先算完全图能吃多少边，再加1。

最容易栽跟头的是忽略'非连通'这个前提，直接套用连通图公式 n(n-1)/2=28 去算，得出 n≈8.2 就选 C 或 B，或者误以为 K8 本身就是答案。还有人会混淆有向图和无向图公式，把 n(n-1) 当成无向完全图去解，导致算出 n=8 就以为够了。其实 K8 是连通的，题目要求非连通，必须拆成至少两个块，所以得再加一个孤立点。

【考点】图论基础｜非连通图性质｜完全图边数公式（n(n-1)/2）｜度约束（∑deg=2|E|）

1. 命题人怎么挖坑

GESP七级图论模块，卡住的是'非连通'这个关键约束。很多考生只盯着'最少顶点'就默认连通图，忽略了必须拆成两个分量。命题人喜欢用'非连通'四个字把简单计算题变复杂，让你以为要搞什么复杂结构，其实最优解往往是最极端的情况：一个分量尽可能'吃边'，另一个分量尽可能'省顶点'。