If all edge weights are distinct, then the MST is unique

  • Comp Sci
  • Thread starter CGandC
  • Start date
In summary, the theorem states that if there are multiple MSTs with the same weight for each edge, then the edges of the MSTs must be the same.
  • #1
CGandC
326
34
Homework Statement
This is not a homework question, I thought about it myself and was wondering if the uniqueness of an MST is defined in terms of edge uniqueness or weight uniqueness
Relevant Equations
- Assume graph is connected and undirected with weight function w: E ->R
- MST = minimum spanning tree
I was having trouble understanding what "uniqueness" means when we talk about MSTs, here's the theorem and its proof:

1685611498130.png

( Source: Jeff Erickson, Algorithms. https://jeffe.cs.illinois.edu/teaching/algorithms/book/07-mst.pdf )

I don't fully understand what "unique" stands for when talking about MSTs. I thought it meant that all the edges of the different MSTs must be the same, not only the weights.

To clarify:
I know that the multiset of weights of all MSTs of a graph must be equal, so if there's an MST with all weights unique then it must be so in every other MST; the question is - are the edges also unique?
If the answer's 'yes' , then how do we conclude from the proof above that the edges must be equal in ## T_1 ## and ## T_2 ##?
If the answer's 'no', then what is a necessary and sufficient condition for all the edges of MSTs to be equal? ( i.e. the MSTs to be unique in terms of the edges themselves )

From the proof above it seems uniqueness is defined in terms of weight of edges, but it feels to me a little bit odd, hence I'm asking the question to have a second opinion on this.

Thanks in advance for any kind of help!
 

Attachments

  • 1685611384621.png
    1685611384621.png
    44.4 KB · Views: 125
Physics news on Phys.org
  • #2
The weights are defined by the graph, not by the spanning tree, so it does not make sense to talk about the weights of the spanning trees being different.
Furthermore, the second paragraph of the proof states "Each of our spanning trees must contain an edge that the other tree omits." This confirms that an edge difference is required for two spanning trees to be different.
 
  • #3
FactChecker said:
The weights are defined by the graph, not by the spanning tree, so it does not make sense to talk about the weights of the spanning trees being different.

Agreed, it's known that the multiset of edge weights of every MST are the same, hence if all the weights of one MST are unique, so are for the other MST.

FactChecker said:
Furthermore, the second paragraph of the proof states "Each of our spanning trees must contain an edge that the other tree omits." This confirms that an edge difference is required for two spanning trees to be different.

That's correct, if we'll assume otherwise we'll have that all edges in ## T ## and ## T' ## are the same, hence ## T = T' ## which is a contradiction to the assumption that ## T \neq T' ##
But I don't understand where's the contradiction in the above proof if we consider the only case left which is "Each of our spanning trees must contain an edge that the other tree omits."

It seems to me the proof above only showed that if we have two different msts where the edge weights are unique, then we can swap an edge from both trees that have the same weight; where's the contradiction here to the assumption that ## T \neq T' ##?
 
  • #4
CGandC said:
But I don't understand where's the contradiction in the above proof if we consider the only case left which is "Each of our spanning trees must contain an edge that the other tree omits."
This must lead to a contradiction, therefore proving that there is no edge in one that is not in the other.
At the end of the proof, it says "##w(e)=w(e'')##". But ##e \ne e''## and the weights are all distinct, so that is a contradiction. The MSTs must be identical.
 
  • Like
Likes CGandC
  • #5
FactChecker said:
This must lead to a contradiction, therefore proving that there is no edge in one that is not in the other.
At the end of the proof, it says "##w(e)=w(e'')##". But ##e \ne e''## and the weights are all distinct, so that is a contradiction. The MSTs must be identical.
Thanks for putting the time and helping me. I overthought about it and after taking a break and coming back to the proof I understand it.
 
  • Like
Likes FactChecker

FAQ: If all edge weights are distinct, then the MST is unique

What does it mean for all edge weights to be distinct in a graph?

In a graph, having all edge weights distinct means that no two edges have the same weight. Each edge has a unique value assigned to it, which differentiates it from all other edges in terms of weight.

Why does having distinct edge weights guarantee a unique MST?

When all edge weights are distinct, there is no ambiguity in choosing the edges to form the Minimum Spanning Tree (MST). At each step of algorithms like Kruskal's or Prim's, the choice of the next edge to include in the MST is clear and deterministic, leading to a unique MST.

Can a graph with non-distinct edge weights have a unique MST?

Yes, a graph with non-distinct edge weights can still have a unique MST, but it is not guaranteed. The uniqueness of the MST in such cases depends on the specific structure of the graph and the distribution of the edge weights.

How do common MST algorithms handle distinct edge weights?

Common MST algorithms like Kruskal's and Prim's handle distinct edge weights straightforwardly. Kruskal's algorithm sorts all edges by weight and adds the smallest edge that does not form a cycle, while Prim's algorithm grows the MST by adding the smallest edge connecting the tree to a new vertex. With distinct weights, these choices are unambiguous, ensuring a unique MST.

Is it possible to have multiple MSTs in a graph with distinct edge weights?

No, it is not possible to have multiple MSTs in a graph with distinct edge weights. The distinct weights ensure that there is only one way to choose the edges that form the MST, leading to a unique minimum spanning tree.

Back
Top