同一张图的两个最小生成树可以具有不同的边权重吗? [英] Can two Minimum Spanning Trees for the same graph have different edge weights?

问题描述

图可以具有许多不同的最小生成树(MST)，但是不同的MST是否可以具有不同的边缘权重集?例如，如果某个MST使用边缘权重{2,3,4,5}，那么每个其他MST是否都必须具有边缘权重{2,3,4,5}，还是其他MST可以使用其他权重集合吗?

给我一​​个想法的特性是，只有边缘权重不同时，图形才具有唯一的MST.

解决方案

集合必须具有相同的权重.这是一个简单的证明:假设他们没有.让我们将T1和T2设为具有不同边权重的不同集合的某些图G的MST.

将这些边缘按重量的升序排列.由于两个权重的多元集不相同，因此请查看权重首先出现分歧的地方.最终在T1或T2中将有最小的权重w *(假设WLOG，它在T1中)，其中T1和T2的所有权重的边数相同，小于w *，但是T1的权重边数多于w * *比T2.直观地讲，权重w *的边缘是T1领先"于T2的位置.

现在，考虑T1中权重w *的边的集合；我们称它们为W *.请考虑将任何这些边添加到T2中时会发生什么.每次执行此操作时，都会在T2中关闭一个周期.请注意，新添加的边e不能是该循环上的最大权重边；如果是，那么通过周期属性，我们可以保证e不会出现在任何MST中，但我们知道它在一个MST中(即T1).因此，循环上必须有一些权重大于或等于w *的边.

如果这些边缘之一的权重严格大于w *，那么我们可以通过删除该边缘来降低T2的成本.不过，这将是不可能的，因为我们知道T2是MST.

因此，我们知道循环中还有一些其他边的权重等于w *.如果这些边缘中的任何一个不在T1中，则选择任何一个并将其删除.请注意，我们只是将T2中的一条边换成了T1中的等权边.因为T1中的权重w *的边比T2中的多，所以我们不能永远这样做，最终我们会遇到以下情况:循环已关闭，并且所有最大权重边均权重为w *，并且来自T1.

那么在这种情况下会发生什么?好吧，考虑一下当我们添加触发它的边时关闭的循环C.我们将证明，在这种情况下，T1不能成为MST，这与我们最初的假设相矛盾，并给了我们想要的结果.

让C *为C中成本低于w *的一组边.按权重顺序处理这些边缘，一次将它们添加到T1中.每次这样做，我们都会关闭一个周期.该循环中的最大权重边缘不能是我们从T2添加的边缘(因为否则，由于循环属性，该边缘首先不应该在T2中出现).因此，最大权重边缘的权重大于T2的边缘的权重(在这种情况下，我们将其删除，与T1是MST相矛盾)，或者它具有相同的权重.最终，我们最终对T1进行了变换，以使它具有比W2少的w *的相同边集.但这是一个问题，因为到那时我们知道在T1中会出现周期C，这意味着T1不是MST.这给了我们我们需要的矛盾.

希望这会有所帮助！

A graph can have many different Minimum Spanning Trees (MSTs), but can different MSTs have different sets of edge weights? For example, if an MST uses edge weights {2,3,4,5}, must every other MST have edge weights {2,3,4,5}, or can some other MST use a different collection of weights?

What gave me the idea is property that a graph has no unique MST only if its edge weights are different.

解决方案

The sets must have the same weight. Here's a simple proof: suppose they don't. Let's let T1 and T2 be MSTs for some graph G with different multisets of edge weights.

Sort those edges into ascending order of weight. Since the two multisets of weights aren't the same, look at where the weights first diverge. There will end up being some smallest weight w* in either T1 or T2 (assume WLOG, that it's in T1) where T1 and T2 have the same number of edges of all weights less than w*, but T1 has more edges of weight w* than T2. Intuitively, edges of weight w* is where T1 "gets ahead" of T2.

Now, consider the set of edges of weight w* in T1; let's call them W*. Consider what happens when you add any of those edges into T2. Every time we do this, it will close a cycle in T2. Note that the newly-added edge e can't be the maximum-weight edge on that cycle; if it were, then by the cycle property we'd be guaranteed that e can't appear in any MST, but we know for a fact that it is in one (namely, T1). Therefore, there must be some edge on the cycle whose weight is greater than or equal to w*.

If one of those edges has weight strictly greater than w*, then we can decrease the cost of T2 by deleting that edge. That would be impossible, though, because we know that T2 is an MST.

Therefore, we know that there is some other edge in the cycle whose weight is equal to w*. If any of those edges are not in T1, then choose any one and remove it. Notice that we've just swapped an edge in T2 for an equal-weight edge in T1. Because there are more edges of weight w* in T1 than in T2, we can't do this forever and eventually we'll run into the case where the cycle was closed and all the max-weight edges are of weight w* and come from T1.

So what happens in this case? Well, think about the cycle C that was closed when we added the edge that triggered this. We're going to show that in this case, T1 can't be an MST, contradicting our initial assumption and giving us the result we want.

Let C* be the set of edges in C that have cost less than w*. Process those edges in order of weight, adding them to T1 one at a time. Each time we do so, we close a cycle. The max-weight edge in that cycle can't be the edge we added from T2 (because otherwise by the cycle property that edge shouldn't have been in T2 in the first place). Therefore, either the max-weight edge either has weight greater than the edge from T2 (in which case we delete it, contradicting that T1 was an MST) or it has the same weight. Eventually, we end up transforming T1 so that it has the same set of edges of cost less than w* that T2 does. But that's a problem, because at that point we know that we would have the cycle C arising in T1, meaning that T1 isn't an MST. This gives us the contradiction we need.

Hope this helps!

这篇关于同一张图的两个最小生成树可以具有不同的边权重吗?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！