最小生成树：剪切属性到底是什么？
我花了很多时间阅读有关最小生成树的割性质的在线演示和教科书。我真的不明白它想要说明什么，甚至不明白它为什么实用。据说它有助于确定向 MST 添加哪些边，但我不明白它是如何实现这一点的。到目前为止，我对剪切属性的理解是，将 MST 分成两个任意子集。这里有什么帮助吗？谢谢！
I've been spending a lot of time reading online presentations and textbooks about the cut property of a minimum spanning tree. I don't really get what it's suppose to illustrate or even why it's practical. Supposedly it helps determine what edges to add to a MST, but I fail to see how it accomplishes that. My understanding of the cut property so far is that you split a MST into two arbitrary subsets. Any help here? Thanks!
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（4）
连接图的割是边的最小集合，其移除将图分成两个组件（片）。最小割属性表示，如果割的一条边的权重小于割中任何其他边的权重，则它位于 MST 中。为了看到这一点，假设存在一个不包含边的 MST。如果我们将边添加到 MST 中，我们会得到一个至少两次穿过割点的循环，因此我们可以通过从 MST 中删除另一条边来打破循环，从而生成权重较小的新树，从而与MST。
A cut of a connected graph is a minimal set of edges whose removal separate the graph into two components (pieces). The minimal cut property says that if one of the edges of the cut has weight smaller than any other edge in the cut then it is in the MST. To see this, assume that there is an MST not containing the edge. If we add the edge to the MST we get a cycle that crosses the cut at least twice, so we can break the cycle by removing the other edge from the MST, thereby making a new tree with smaller weight, thereby contradicting the minimality of the MST.
我想分享一下我对 Cut Property 的理解，以提供帮助。如果我的帖子有任何需要改进的地方，请在下面评论，以便我修改我的答案。
为了简化，假设在图 G(V, E) 中形成了 2 个独立的 MST（T1 和 T2）。 T1 和 T2 之间还有尚未连接的边。
我们想要证明，当 T1 和 T2 连接时，新生成的树也是 MST——最优解。
在 T1 和 T2 之间尚未连接的边中，选择最亮的边。添加它来连接 T1 和 T2 形成一个新的 MST - 一个最佳解决方案。
注意：连接同一棵树中的边会引入环路。但树不应该包含循环
I'd like to share what I understand about Cut Property to help. If there're anything to improve in my post, please comment below so I can modify my answer.
For simplification, suppose there are 2 separate MSTs (T1 and T2) formed in a graph G(V, E). There are edges not yet connected between T1 and T2.
We want to show that when T1 and T2 are connected, a newly produced tree is also an MST - an optimal solution.
Among the edges not yet connected between T1 and T2, pick the lightest edge. Adding it to connect T1 and T2 makes a new MST - an optimal solution.
Note: Connecting an edge in the same tree introduces a cycle. But a tree shouldn't contain a cycle
这个解释是基于另一个属性的。
“对于任何切割，如果有偶数个边穿过切割，那么一定有一个循环穿过切割”
因为 MST 不包含任何循环，所以不会有任何偶数个边穿过切割。
反证法：
假设有一个 MST 不包含最小权重为“e”的边。如果我们将边“e”添加到 MST，我们就会得到一个至少两次穿过切口的循环。我们可以删除权重较大的其他边并打破循环，从而产生包含较小权重边“e”的 ST。这与假设相矛盾。
There's another property up on which this explanation is based.
"For any of the cut, if there are even number of edges crossing the cut then there must be a cycle crossing the cut"
Because MST does not contain any cycle there won't be any even number of edges crossing the cut.
Proof by contradiction:
Assume that there's a MST not containing edge with min weight "e". If we add the edge "e" to the MST we get a cycle crossing the cut at least twice. We can remove other edge with more weight and break the cycle which results in an ST containing lesser weighing edge "e". This is in contradiction with the assumption.
在直观层面上，割属性旨在告诉你，如果确实有2个集合S和S'，那么连接这两个集合的是权重最小的边。
如果我们想做一个简单的例子，那么假设有两条边，一条权重为 2，另一条权重为 1。两条边都连接 S 和 S'。我可以选择边权重为 2 的边来连接 S 和 S' 并创建生成树。然而，如果我这样做，生成的生成树不是最小的，因为边权重为 1，可用于降低连接它们的成本，而不是使用边权重 2。当权
重最小的边用于连接 S 和 S'，最终结果是最小生成树，因为我们保留了最小属性。
At the intuitive level, the cut property aims to tell you that if there is indeed 2 Sets S and S', then what connects the two sets is the edge that weighs the least.
If we want to make a simple example, then say there are two edges one with weight 2 and another weight 1. Both edges connect S and S'. I can choose the edge that have edge weight 2 to connect S and S' and create a Spanning Tree. If I do that however, the resulting Spanning Tree is not Minimum because there is the edge weight of 1 that can be used to lower the cost of connecting them instead of using edge weight of 2.
When the edge with the least weight is used to connect S and S', the end result is a Minimum Spanning Tree because we kept the Minimum property in place.