我已经花了很多时间阅读关于最小生成树的割边性质的在线演示和教科书。我真的不明白它应该说明什么，甚至不知道它有什么实际用途。据说它有助于确定要添加到MST的边，但我看不出它是如何做到的。到目前为止，我对割边性质的理解是将一个MST分成两个任意的子集。请问有什么帮助吗？谢谢！
3个回答
77
连接图的割是一组最小的边，它们的删除将该图分成两个部分（片）。最小割定理说明，如果割中的某条边的权重比割中的任何其他边都要小，则该边属于最小生成树。为了看清这一点，假设存在一个不包含该边的最小生成树。如果我们将该边添加到最小生成树中，我们会得到一个穿过割至少两次的环，因此我们可以通过从最小生成树中删除另一条边来打破循环，从而形成一个更小重量的新树，这与最小生成树的极小性矛盾。
- deinst
6
18年后，我仍然对此毫无头绪。你能否像我还是个孩子一样向我解释一下？ - Alexander Falk
@AlexanderFalk 你在解释的哪个部分有困难？ - deinst
1抱歉，我有两个问题：（1）为什么“割”会两次穿过新添加的边？（2）如果新添加的边的权重小于要删除的“其他”边的权重，则它仍将是最小生成树，为什么存在矛盾？ - user2994783
@user2994783：（1）MST的一条边必须已经在割中（=“跨越”），否则就没有办法从一侧的顶点到达另一侧的顶点，在MST中，您可以从任何顶点到达任何其他顶点；添加新的较小边后，现在有2条边在割中（=“交叉”）。 （2）矛盾之处在于它本来就不可能是 MST，因为我们刚刚减少了它的权重。 - j_random_hacker
最小生成树不包含割中的每条边吗？ - Foobar
1@Roymunson 假设我们使用切割 P 和 Q 将图形分成两个集合。将两个圆标记为 P 和 Q，并在这两个圆之间绘制 4 条线，例如表示我们的切割集合。想象一下，如果最小生成树中包含了其中两条线路，那么我们可以从 P 到 Q 再返回 P，这样就形成了一个循环。根据树的定义（即无环），这是不允许的。这意味着切割集合中的边是互斥的。这意味着我们应该选择最小的那个（我们可以通过反证法证明）。 - Neel Sandell
1
这个解释基于另一个属性。
“对于任何一次切割，如果穿过切割的边数为偶数，则必定存在一条穿过切割的循环。”
因为MST不包含任何循环，所以不会有任何偶数条边穿过切割。
反证法证明： 假设存在一个不包含最小权重“e”的边的MST。如果我们将边“e”添加到MST中，我们会得到至少穿过切割两次的循环。我们可以删除其他权重更大的边并打破循环，从而得到一个包含较小权重边“e”的ST。这与假设相矛盾。
“对于任何一次切割，如果穿过切割的边数为偶数，则必定存在一条穿过切割的循环。”
因为MST不包含任何循环，所以不会有任何偶数条边穿过切割。
反证法证明： 假设存在一个不包含最小权重“e”的边的MST。如果我们将边“e”添加到MST中，我们会得到至少穿过切割两次的循环。我们可以删除其他权重更大的边并打破循环，从而得到一个包含较小权重边“e”的ST。这与假设相矛盾。
- Chaitanya Kiran Gubbala
1
我想分享一下我对Cut Property的理解，希望能够帮到你。如果我的回答有需要改进的地方，请在下面评论，这样我就可以修改我的答案。
我们希望展示当T1和T2相连时，新产生的树也是MST——最优解。
在T1和T2之间尚未连接的边中，选择最轻的边。将其添加到连接T1和T2的边会生成一个新的MST-最优解。
注意：在同一棵树中连接边会引入循环。但是一棵树不应该包含循环。
Background:
为简化起见，假设在图G（V，E）中形成了2个独立的最小生成树（T1和T2）。 T1和T2之间还有尚未连接的边。
Goal:
我们希望展示当T1和T2相连时，新产生的树也是MST——最优解。
>> My Understanding of Cut Property:
在T1和T2之间尚未连接的边中，选择最轻的边。将其添加到连接T1和T2的边会生成一个新的MST-最优解。
注意：在同一棵树中连接边会引入循环。但是一棵树不应该包含循环。
- LED Fantom
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接