带权无向图不同最小生成树的边替换性质证明问询

先梳理已知前提：

• G是带权无向图，T、T'是G的两个不同最小生成树
• e ∈ T且e ∉ T'，已证得w(e) = w(e')（e'是待找的T'\T中的边）
• 删除e后，T被拆分为两个连通分量A和B，T_new要成为树，必须选连接A、B的边

一、证明满足条件的e'必然存在 #

我们可以从MST的连通性和权值最优性两个角度推导：

1. 因为T'是G的生成树，它必须连通A和B（否则T'无法覆盖G的所有顶点），所以T'中至少存在一条边e'，使得e'的两个端点分别在A和B中。
2. 接下来证明e' ∉ T：
   • 假设e' ∈ T，那么在T中，e和e'都是连接A和B的边，但树中任意两个连通分量之间只能有唯一一条边（否则会形成环），这和T是树矛盾，因此e'必然属于T'\T。
3. 最后确认w(e') = w(e)：
   • 因为T是MST，所有连接A和B的边的权值都≥w(e)（否则把e换成这条边，T的总权值会更小，与T是MST矛盾）。
   • 因为T'是MST，所有连接A和B的边的权值都≤w(e)（否则把T'中的e'换成e，T'的总权值会更小，与T'是MST矛盾）。
   • 结合两者，只能是w(e') = w(e)。

综上，这样的e'必然存在。

二、确定具体的e' #

满足条件的e'就是T'中所有连接A和B的边（至少有一条）。你可以通过以下方式定位：

• 遍历T'中的边，找到任意一条一个端点在A、另一个在B的边即可。
• 结合你提到的「生成包含最多黄色边的MST」算法：把T中除e外的所有边标记为黄色，运行该算法时，当黄色边构建出A和B两个连通分量后，算法会在权值等于w(e)的边中选择一条连接A和B的边——这条边要么是e（对应T），要么就是T'中的e'（对应另一个MST），这也印证了e'的存在性和具体位置。

三、验证T_new是MST #

把T中的e替换为e'后：

• T_new仍然是生成树：它连通所有顶点（e'连接了A和B），且无环（因为T中删除e后无环，加入e'不会形成环——如果形成环，说明T中存在从e'一个端点到另一个端点的路径，但这条路径必然经过e，而我们已经删除了e，所以不可能形成环）。
• T_new的总权值和T相同：w(e) = w(e')，所以总权值不变，因此T_new也是G的最小生成树。

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