GESP 八级 · GESP202609 C++ 八级 第 18 题

若一个连通无向图的最小生成树中存在权值相同的边，则最小生成树一定不唯一。

看到"最小生成树是否唯一"这类命题，第一反应是回忆Kruskal算法的贪心策略——按边权从小到大排序，依次选取不构成环的边。唯一性判定的核心定理是：MST唯一当且仅当所有边权互不相同。因此解题通法是"找反例"：只要构造一个连通图，其MST里存在两条权值相同的边，就能证明命题成立。

选项B的陷阱在于把"存在相同权值边"与"MST唯一"的关系搞反。命题人利用考生对Kruskal算法的机械记忆，误以为"边权相同就一定会被同时选中"，从而认为MST一定不唯一。但真正决定唯一性的不是边权是否相同，而是这些相同权值的边是否都能同时出现在某棵MST里。若相同权值边中只有一条被选中，其余被跳过，MST仍可能唯一。

1. 考纲定位

本题考查《GESP 考试大纲》图论模块中"最小生成树"的判定与性质，属于八级核心考点。命题人放这道题，就是要卡住考生对Kruskal算法唯一性定理的掌握——绝大多数人只会背"贪心选边"，却忽略了"边权互异"才是唯一性的充要条件。

2. 解题思维

看到"最小生成树是否唯一"这类命题，第一反应是回忆Kruskal算法的贪心策略——按边权从小到大排序，依次选取不构成环的边。唯一性判定的核心定理是：MST唯一当且仅当所有边权互不相同。因此解题通法是"找反例"：只要构造一个连通图，其MST里存在两条权值相同的边，就能证明命题成立。