- #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:
( 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!
( 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!