第 6 题
在具有 n 个顶点的图 G 中，若最小生成树不唯一，则（ ）。
A. G 的边数一定大于 n-1 B. G 的权值最小的边一定有多条 C. G 的最小生成树代价不一定相等 D. 上述选项都不对
[tag_link]
正确答案：A
最小生成树（MST）不唯一意味着图 G 中存在至少两个不同的生成树，它们的总权值相同且都是最小的。 选项 A 指出 G 的边数一定大于 n-1。 这是因为如果图 G 的边数等于 n-1，则 G 本身是一棵树，其生成树唯一，与 MST 不唯一矛盾。 因此，要存在多个 MST，图 G 必须有多余的边，即边数至少为 n，故边数大于 n-1 必然成立。 选项 B 错误，因为 MST 不唯一并不要求权值最小的边有多条。 例如，一个包含三个顶点、边权分别为 1、2、2 的图，最小权值边只有一条（权值 1），但存在两个 MST（总权值均为 3）。 选项 C 错误，因为所有最小生成树的代价必须相等，否则其中代价较大的就不是“最小”生成树。 综上，选项 A 正确。