🏷️ 知识点：MST唯一性
任何一个无向连通图的最小生成树（ ）。
A. 有一棵或多棵 B. 只有一棵 C. 一定有多棵 D. 可能不存在
[tag_link]
正确答案：A
结论
选 A。无向连通图至少存在一棵最小生成树，但权值相同时可能存在多棵。
推导
连通图可通过不断选取不成环的边得到生成树，有限棵生成树中总权值最小者即为 MST；若不同边组合具有相同最小代价，MST 不唯一。
易错点
连通性保证存在性，不保证唯一性；D 把“可能不唯一”误解成“可能不存在”。
下列关于图的生成树和最小生成树的叙述中，正确的是（ ）。
A. 只要无向连通图中没有权值相同的边，则其最小生成树唯一 B. 只要无向图中有权值相同的边，则其最小生成树一定不唯一 C. 从 n 个顶点的连通图中选取 n-1 条权值最小的边，即可构成最小生成树 D. 设连通图 G 含有 n 个顶点，则含有 n 个顶点、n-1 条边的子图一定是 G 的生成树
[tag_link]
正确答案：A
结论
选 A。
推导
无向连通图所有边权互异时，Kruskal 或 Prim 每一步的最小合法边唯一，故 MST 唯一。B 中等权边不一定参与竞争；C 只按权值选边可能成环；D 还需满足连通性。
易错点
“n 个顶点、n−1 条边”只是树的必要数量条件，不足以保证无环且连通。
设有 n 个顶点的无向连通图的最小生成树不唯一，则下列说法中正确的是（ ）。
A. 图的边数一定大于 n-1 B. 图的权值最小的边一定有多条 C. 图的最小生成树的代价不一定相等 D. 图的各条边的权值不相等
[tag_link]
正确答案：A
结论
选 A。MST 不唯一时，原图不可能本身就是唯一的 n−1 条边树，因此边数必大于 n−1。
推导
所有 MST 的代价都等于全局最小代价，故 C 错；导致不唯一的等权边不必是全图最小权边，B 错；D 与不唯一相矛盾，边权全异反而保证唯一。
易错点
树形不唯一与最小代价不唯一是两回事：MST 可以有多棵，但代价必相同。