🏷️ 知识点：生成树代价

设有 n 个顶点的无向连通图的最小生成树不唯一，则下列说法中正确的是（　　）。

A. 图的边数一定大于 n-1 B. 图的权值最小的边一定有多条 C. 图的最小生成树的代价不一定相等 D. 图的各条边的权值不相等

[tag_link]

正确答案：A

结论

选 A。MST 不唯一时，原图不可能本身就是唯一的 n−1 条边树，因此边数必大于 n−1。

推导

所有 MST 的代价都等于全局最小代价，故 C 错；导致不唯一的等权边不必是全图最小权边，B 错；D 与不唯一相矛盾，边权全异反而保证唯一。

易错点

树形不唯一与最小代价不唯一是两回事：MST 可以有多棵，但代价必相同。