🏷️ 知识点：极值构造

具有 51 个顶点和 21 条边的无向图的连通分量最多为（ ）。

A. 33 B. 34 C. 45 D. 32

[tag_link]

正确答案：C

结论

最多有 45 个连通分量。

推导

要让连通分量尽可能多，应把边集中在尽量少的顶点上。21 条边可由完全图 (K_7) 提供，因为 (\binom{7}{2}=21)。其余 44 个顶点均孤立，因此连通分量数为 (1+44=45)。

易错点

不要把 21 条边简单地当作 21 个分量；一条边会把两个顶点合并到同一个连通分量。极值构造应优先使用边数恰好足够的完全图，再保留孤立点。