algorithm - 在图中找到最小生成树（MST）？

Question

给定一个边上有权G重的无向图和 2 个different最小生成树：T, T'

然后我想证明以下几点：

对于 T 中不在 T' 中的每条边e，在 T' 中都有一条不在 T 中的边e'，因此如果我们e用e'in T 替换（我们称之为 T_new），那么它仍然是 的最小生成树G。

我认为我离找到正确的算法太近了，但有点卡住了：

1. 我已经证明weight(e)必须完全等于weight(e')。

2. 由于 T 是一棵树，删除 e 将导致 2 个分离的组件，然后 T_new 要成为一棵树，它必须使用连接来自这些不同组件的两个顶点的边之一。

但是，我无法知道哪个边缘e'会起作用。另外，我无法证明总是存在这样的优势（我只是发现e'必须满足一些要求）。

一些注意事项：我知道 Kruskal 算法，并且熟悉一种算法，在该算法中我们可以用黄色绘制一些边缘并要求它生成具有最大黄色边缘的最小生成树（换句话说，从所有找到的最小生成树中返回具有最大数量的树黄色边缘）

标签： algorithmgraphtreeminimum-spanning-treekruskals-algorithm

Answer 1

让T1和T2成为 的两个连通分量T \ {e}。考虑连接inP端点的路径。由于连接and ，所以连接 and ，因此在连接and中存在一条边。边缘不能比 轻，否则不会是最小值 ( )。边缘不能重于，否则不会是最小值 ( )。eT'eT1T2Pe'PT1T2e'eTT \ {e} U {e'}e'eT'T' \ {e'} U {e}