图的唯一性：为何需向MST B添加边e1构造环？相关技术疑问

当图中所有边权重唯一时，存在唯一的最小生成树（MST）。该结论可推广至生成森林，也适用于电信公司路径成本规划等现实场景。

原唯一性证明过程 #

1. 假设存在两个不同的MST A和B；
2. 由于A、B包含相同节点但结构不同，必然存在仅属于其中一个的边。取这些边中权重最小的e1（因权重唯一，e1的选择是唯一的），假设e1属于A；
3. 因为B是MST，将e1加入B后必然形成一个包含e1的环C；
4. 树A本身无环，因此环C中一定存在不属于A的边e2；
5. 由于e1是仅属于A或仅属于B的边中权重最小的，因此e2的权重大于e1；
6. 在B中用e1替换e2，会得到一棵权重更小的生成树；
7. 这与B是MST的假设矛盾，因此不存在两个不同的MST，即MST唯一。

技术问询解答 #

不能跳过向B添加e1的步骤，直接取B中最小边来证明MST的唯一性。

原因在于：原证明中e1的定义是仅属于A或仅属于B的边中权重最小的那条，而B中的最小边是整个图的全局最小边（所有MST都会包含这条边，因此它必然同时属于A和B），二者的定义完全不同。如果跳过添加e1构造环的步骤，无法建立e1与B中某条非共有边的关联——我们必须通过环C找到B中存在的、权重比e1大的边e2，才能完成替换操作并导出矛盾。直接取B的最小边的话，这条边是A和B共有的，无法用来构建和e1的权重对比关系，自然无法完成唯一性的证明。

内容的提问来源于stack exchange，提问作者John Stuart