algorithm - MST 切割的最小重量

Question

令 G 为具有不同边权重的无向图。令 T 为 G 中的 MST。令 (u, v) 为 T 中的任何边。证明存在一个割 (S;VS) 使得 (u;v) 是该割中权重最小的边。

Answer 1

我给它一个镜头，让我们考虑一个切割，这样 e = (u, v) 是它唯一属于 T 的边。假设切割中有另一个边 e' 且 w(e') < w(e )，然后我们可以形成另一个ST，包括e'和删除e，这将具有更小的权重，荒谬的。

Answer 2

我们从 |V| 开始 削减。我们在每个循环中合并两个切割。最后，我们以 1 个剪辑结束。MST 是此切割中边的子集。因此，对于每次合并，我们为该切割选择了（一个）轻边缘（u，v）。最后，我们有|V|-1 条边。相反，对于树中的每个边缘，都有一个“桥接”的切口。因此，如果边缘 (u,v) 在 MST 中，则有一个切口 (S,VS) 对应于它是轻边缘。