题目

使用 Prim（普里姆）算法求带权连通图的最小（代价）生成树（MST）。请回答下列问题：

(1) 对下列图 G，从顶点 A 开始求 G 的 MST，依次给出按算法选出的边。

(2) 图 G 的 MST 是唯一的吗？

(3) 对任意的带权连通图，满足什么条件时，其 MST 是唯一的？

解析

(1) 从 A 出发的 Prim 选边过程

答案：依次选出的边为 A-D(4)、D-E(4)、C-E(5)、B-C(4)，MST 总权重 17。

Prim 算法：维护"已加入 MST 的顶点集 V_T"，每轮从"V_T 一端在内、另一端在外"的所有边中选权值最小的一条加入。下表逐轮模拟：

轮	V_T	候选横切边（权）	选出	加入 V_T
起		A-B(6), A-D(4), A-E(5)	A-D(4)	D
2		A-B(6), A-E(5), D-C(6), D-E(4)	D-E(4)	E
3		A-B(6), C-D(6), C-E(5)	C-E(5)	C
4		A-B(6), B-C(4)	B-C(4)	B

V_T = {A, B, C, D, E} 全员到齐，MST 边集 = {A-D, D-E, C-E, B-C}，权重 4+4+5+4 = 17。

(2) 该图 MST 是否唯一

答案：唯一。

证明思路：把所有边按权值排序为 A-D(4), B-C(4), D-E(4), A-E(5), C-E(5), A-B(6), C-D(6)。沿 Kruskal 思路考察：

• 三条权 4 的边：A-D、B-C、D-E。它们彼此不形成环（覆盖顶点 {A,D,B,C,E} 但只有 4 条边连接，不可能成环），所以 MST必须全选这三条；
• 选完后两个连通分量 {A, D, E} 与 {B, C}，需再加一条边连通；
• 候选边按权值升序：A-E(5)、C-E(5)。A-E 两端都在 {A,D,E} 内 → 必形成环、不可选；只剩 C-E 唯一可选。

每一步候选都唯一，所以 MST 唯一。

(3) 任意带权连通图 MST 唯一的充分条件

答案：当图中所有边的权值互不相同时，MST 一定唯一。

证明思路（反证）：若 MST 不唯一，存在两棵不同的 MST 、。取它们的对称差中权值最小的边 ，不妨设 。把 加入 会形成一个环 C，C 中至少有一条不在 的边 。由于所有边权互不相同，要么 （用 换 让 变更轻 → 与 是 MST 矛盾），要么 （用 换 让 变更轻 → 矛盾）。两种情况都不可能，故 MST 唯一。

编者注（生僻术语）：「边权互不相同」是 MST 唯一的充分非必要条件——本题就是反例：有 3 条权 4 的边，权值并不全异，但 MST 仍唯一（因为这 3 条边都"独立"地必须选）。更精确的等价条件涉及"切（cut）的最小边唯一"，考研不要求掌握，写"权值互不相同时 MST 唯一"就拿满分。