GESP 七级 · GESP 202412 C++ 七级 第 8 题

一个简单无向图有 10 个结点、6 条边。在最差情况，至少增加多少条边可以使其连通？（ ）

图的存储方式：邻接矩阵（O(n²)空间，适合稠密图）、邻接表（O(n+m)空间，适合稀疏图）。

有向完全图边数为n(n-1)，无向完全图边数为n(n-1)/2。简单图不含自环和重边。

【考点】图连通分量｜生成树边数｜最差情况分析

解题思维：10个节点无向图最多可拆成10-m个分量（每边最多减1），本题m=6，最坏情形下分量数=10-6=4。要使4个分量连通至少需加3条边（k个分量需k-1条边）。

陷阱拆解：错误选项D(9条)源于误以为6条边能形成6个独立边，却忽略了10个节点的限制，实际最多形成4个分量。命题人特意用"最差情况"诱导考生忽略边的连接效率，只数孤立点。

反命题思维：若节点数不变边增至7条，最坏只剩3个分量需2条边；若边达到9条，图已连通无需加边。这类题本质是求"n-m"的最大值。