请回答下列问题：

(1) 试证明若图中各条边的权值各不相同，则它的最小生成树唯一。 (2) Prim 算法和 Kruskal 算法生成的最小生成树一定相同吗？ (3) 画出下列带权图 G 的所有最小生成树。

最小生成树

[tag_link]

**【解析】** (1) 采用反证法证明：假设图中有两个不同的最小生成树 $T_1$ 和 $T_2$ 。设 $e$ 是 $T_1$ 中但不在 $T_2$ 中的权值最小的边。将 $e$ 添加到 $T_2$ 中，会形成一个环，该环中至少存在一条边 $f$ 不在 $T_1$ 中。由于图中各边权值各不相同，比较 $e$ 和 $f$ 的权值。若 $w(f)<w(e)$ ，则在 $T_2$ 中用 $e$ 替换 $f$ 会得到一棵权值更小的生成树，与 $T_2$ 是最小生成树矛盾；若 $w(f)>w(e)$ ，则在 $T_1$ 中用 $f$ 替换 $e$ 会得到一棵权值更小的生成树，与 $T_1$ 是最小生成树矛盾。因此假设不成立，最小生成树唯一。

(2) Prim 算法和 Kruskal 算法都是贪心算法，用于求解最小生成树。当图中边权值各不相同时，最小生成树唯一，因此两种算法必然得到相同的最小生成树。但当图中存在权值相同的边时，最小生成树可能不唯一，两种算法在选择边时可能做出不同选择，从而生成不同的最小生成树。因此，它们生成的最小生成树不一定相同。

(3) 根据 Kruskal 算法，先把 $c-d$ 的边（权值 $20$ ）加入集合，而接下来选择下一条边时，因为有两条权值为 $40$ 的边可以选择，那么因为不同的选择就会生成出不同的最小生成树。若选择 $b-d$ ，然后同样出现 $c-d$ 与 $a-c$ 的选择，而不管先选择哪条边，另一条边也会成为下一个选择的对象，所以这里不影响树的结构，最后答案为左边这棵树；而当之前第二次选择边的时候，选择 $c-b$ 则会是右边的最小生成树。