连接图的一组边中的最小边

Question

以下是我的图论与算法课程中的一个例子：

让A为带权无向图（不同权重）的边的最小子集G，这样，如果我们A从中删除G，G则变得断开连接。中最亮的边A必须位于任何 MST 中。

为什么这是一个正确的事实？我无法理解。

Answer 1

根据最小边割的定义：

最小边切割是这样的边切割：如果将任何边放回到图中，则图将被重新连接。

如下图所示：

集合 A = {a, b, c, d} 是最小边切割。

如果从 G 中删除 A，则图将断开。

现在，属性：“A 中最轻的边必须位于任何 MST 中”可以通过剪切属性来解释：

因此该陈述是正确的，因为，

集合 A = e = min(a, min(b, min(c,d))) 中最轻的边将成为 MST 的一部分。