GESP 七级 · GESP 202603 C++ 七级 第 21 题

在无向连通图中删除一条边，该图就一定变成非连通图。

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

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

【考点】图的连通性｜桥边判定｜反例构造

🎯 考纲定位 考查 GESP 七级图论模块中「连通图性质」与「边分类」的交叉点。命题人专门用这种绝对化表述卡住大量考生——他们死记"树删边必断"，却忽略非树连通图的特殊性。

🧠 解题思维 看到「无向连通图」先想「树」，但树只是连通图的特例；继续想「环」，环上任意边删除后环仍连通；再想「多环图」，删一条边最多破坏一个环，图的连通性依然保持。通法就是：判断命题是否对所有满足条件的图成立，一个反例即可证伪。

🪤 陷阱拆解 选项 A 的陷阱在于偷换概念——把「树」的性质强行推广到所有连通图。最阴险的细节是「就一定」这个绝对化表述，只要存在一个连通图且删某条边后仍连通，命题即假。反例构造只需一个含 3 个以上顶点的环：删任意一条边，剩余图仍是连通的。如果你只背结论、不理解「桥边」与「非桥边」的区别，必然掉进这个坑。

🔄 反命题思维 如果把条件改成「无向树」，答案立刻变 A；如果把「无向连通图」改成「无向连通图且无环」，答案也变 A。刷到此类题时，先问自己：「命题覆盖的边界是什么？有没有特例能证伪它？」