我一直在阅读有关最小生成树的切割属性的在线演示文稿和教科书。我真的不明白它应该说明什么，甚至为什么它是实用的。据说它有助于确定要添加到 MST 的边缘，但我看不到它是如何实现的。到目前为止，我对 cut 属性的理解是将 MST 拆分为两个任意子集。这里有什么帮助吗？谢谢！
问问题
36599 次
3 回答
74
连通图的切割是最小的边集，其删除将图分成两个组件（部分）。最小割属性表示，如果割的一条边的权重小于割中的任何其他边，则它在 MST 中。要看到这一点，假设有一个 MST 不包含边缘。如果我们将边添加到 MST，我们会得到一个至少两次穿过切割的循环，因此我们可以通过从 MST 中移除另一条边来打破循环，从而生成一棵权重更小的新树，从而与最小性相矛盾MST。
于 2010-07-25T02:26:17.377 回答
1
这个解释基于另一个属性。
“对于任何切口，如果有偶数个边缘穿过切口，则必须有一个循环穿过切口”
因为 MST 不包含任何循环，所以不会有任何偶数条边穿过切口。
矛盾证明：假设有一个 MST 不包含最小权重“e”的边。如果我们将边“e”添加到 MST，我们会得到一个循环至少两次穿过切口。我们可以删除其他权重更大的边并打破循环，从而导致 ST 包含较小的权重边“e”。这与假设相矛盾。
于 2019-05-12T11:30:14.937 回答
0
我想分享我对 Cut Property 的理解以提供帮助。如果我的帖子有什么需要改进的地方，请在下面发表评论，以便我修改我的答案。
Background:
为简化起见，假设在图 G(V, E) 中形成了 2 个单独的 MST（T1 和 T2）。T1 和 T2 之间还有尚未连接的边。
Goal:
我们想证明，当 T1 和 T2 连接时，新生成的树也是 MST——最优解。
>> My Understanding of Cut Property:
在 T1 和 T2 之间尚未连接的边中，选择最轻的边。添加它以连接 T1 和 T2 使新的 MST 成为最佳解决方案。
注意：连接同一棵树中的一条边会引入一个循环。但是一棵树不应该包含一个循环
于 2019-03-06T09:44:32.033 回答