🏷️ 知识点：图的连通性

对于无向图 (G=(V,E))，下列选项中，正确的是（ ）。

A. 当 (|V|>|E|) 时，(G) 一定是连通的 B. 当 (|V|<|E|) 时，(G) 一定是连通的 C. 当 (|V|=|E|+1) 时，(G) 一定是不连通的 D. 当 (|V|>|E|+1) 时，(G) 一定是不连通的

[tag_link]

正确答案：D

结论

选项 D 正确：若 (|V|>|E|+1)，则 (|E|<|V|-1)，图不可能连通。

推导

含 (|V|) 个顶点的连通无向图至少需要 (|V|-1) 条边，等号情形就是生成树。D 的条件等价于 (|E|<|V|-1)，违反连通图的必要条件，因此必不连通。

A、B 都不是充分条件：顶点数大于边数时可以有多个孤立顶点；边数大于顶点数时也可以是一个稠密连通分量加孤立顶点。C 也错误，因为 (|E|=|V|-1) 的树就是连通图。

易错点

要区分“连通的必要条件”和“充分条件”。(|E|\ge |V|-1) 只是连通所需的必要条件，不足以保证连通；只有 (|E|<|V|-1) 才能直接推出一定不连通。

若无向图 (G=(V,E)) 含有 7 个顶点，要保证图 (G) 在任何情况下都是连通的，则需要的边数最少是（ ）。

A. 6 B. 15 C. 16 D. 21

[tag_link]

正确答案：C

结论

至少需要 16 条边，选项 C 正确。

推导

要让 7 个顶点仍然不连通，边数最多的构造是一个含 6 个顶点的完全图 (K_6) 加 1 个孤立顶点，最多有 (\binom{6}{2}=15) 条边。因此再增加 1 条边后，不可能保持不连通，保证连通所需的最少边数为

[ \binom{7-1}{2}+1=\binom{6}{2}+1=16。 ]

一般地，7 个顶点的无向图有至少 (\binom{n-1}{2}+1) 条边时必连通。

易错点

不要把连通图的下界 (n-1=6) 当成“无论如何都连通”的保证值；6 条边可以只组成一棵树，也可以分散在多个连通分量中。保证值要从“最密的不连通构造”出发计算。