Will a minimum spanning tree and shortest path tree always share at least one edge?

Question

I'm studying graph theory and I have a question about the connection between minimum spanning trees and shortest path trees.

Let G be an undirected, connected graph where all edges are weighted with different costs. Let T be an MST of G and let T_s be a shortest-path tree for some node s. Are T and T_s guaranteed to share at least one edge?

I believe this is not always true, but I can't find a counterexample. Does anyone have a suggestion on how to find a counterexample?

Weakminded

Are the edge weights necessary non-negative? – Banderillero

Yes, this is always true because of the edges connected to s, the shortest edge among them which is connected to the spanning tree will also be a member of the shortest path tree. – Equitable

@TylerDurden How do you know that one of the edges incident with s in the SPT is also one of the edges incident with s in the MST? – Ronnaronnholm

Answer 1

I think that this statement is actually true, so I doubt you can find a counterexample.

Here's a hint - take any node in the graph and find a shortest path tree for that node. Now consider what would happen if you were to run Prim's algorithm starting from that node - can you guarantee that at least one edge from the MST will find its way into the shortest path tree?

Hope this helps!

Banderillero

Thanks for your reply.I tried to use your method both Kruskal's algorithm and Prim's algorithm but the two trees always share at least one edge – Weakminded

@Julius- Could you prove that after running Prim's algorithm starting from s, you are guaranteed to have at least one edge in common with the shortest-path tree? – Banderillero

I don't think the hint helps in proving or disproving the statement. If I understand you correctly, it suggests that a specific set of MSTs and a specific set of shortest-path-trees always share one edge, not that it's true for all MSTs and shortest-path-trees of any general graph. – Ronnaronnholm

@G.Bach: It sure does help. Give the constraints of the problem another read. – Boisterous

@G.Bach- My intent is that this would be the outline of a general proof - start with a shortest-path tree for any arbitrary node in the graph, then consider the first step of Prim's algorithm starting from the source node of the shortest-path tree. Since the edge weights are unique, there is a unique MST in the graph, so the proof works for arbitrary MSTs. Since we assumed an arbitrary shortest-path tree, this proof also works for arbitrary shortest-path trees. Or am I missing something? – Banderillero

@Banderillero Do you mean the first edge chosen by Prim's algorithm starting from s would also be in any shortest path tree starting from s? – Ronnaronnholm

@G.Bach- That's what I was going for... though I didn't want to explicitly give that away. :-) (I'm also assuming nonnegative edge weights here, which might not actually be the case.) – Banderillero

@Banderillero If the edge weights are non-negative, that is what follows, I agree. With negative edge weights, I don't see it from that argument; but the statement still seems true. – Ronnaronnholm

I still don't understand. This shows that an MST and SPT that are rooted at the same node will always share an edge. But how does it show that an MST and SPT not rooted at the same node always share an edge? – Crownpiece

@BlueRaja-DannyPflughoeft- MSTs are not rooted at any particular node - they're globally unique. Since all the edge weights are distinct, there is only one MST in the graph, so if we were to run any algorithm to find an MST, we'd be guaranteed to get back the same MST. Consequently, I can say that the MST created by running Prim's algorithm starting at the source node s of the SPT is the global MST, so any claims I can make about the MST generated this way would be general. – Banderillero

@BlueRaja-DannyPflughoeft If the edge weights are distinct, the MST is unique, so it's irrelevant at what node you start the MST-algorithm. @ templatetypedef: My first comment actually was ill-phrased since it implies there may be multiple MSTs, which I assumed because I had skipped the part of the OP that said "distinct weights". – Ronnaronnholm

Ah, I missed the fact that the edge weights are distinct. Is this answer still true if not all the edge weights are distinct, I wonder? – Crownpiece

@BlueRaja-DannyPflughoeft No it's not; take the clique over 5 nodes with uniform edge weights, draw it like a pentagram. It should be easy to see two distinct trees, which are both MSTs and SPTs. – Ronnaronnholm

@G.Bach: In your example (assuming by 'clique' you mean 'complete graph'), there is a unique SPT for each node, which contains every edge touching that node (one of which is necessarily in an MST). So, that is not a counter-example.. – Crownpiece

@BlueRaja-DannyPflughoeft (Yes, a clique is a complete simple graph.) No, the SPT is not unique, if all edge weights are 0. My statement was too general, so in general I was wrong. – Ronnaronnholm

@G.Bach: Well, yeah that's trivial, I assumed we were talking about positive edge-weights... – Crownpiece

Answer 2

Proof To vertex s and its shortest-path tree T_s, the wedge in MST T is w(s, v) ,and suppose it doesn't exist in T_s . then there must be a shorter path from v to s,and there is a vertex in the path(because w(s, v) is not the shortest path),which suppose to be p, and makes s->p->v, w(s, v) >= path(s->p->v). Remove w(s, v) and add w(s, p) in T , when all edge are positive and different, w(s, p) < w(s, v). we get a less minimum spanning tree T '.

But T is an MST.Here is the contradiciton. Assumption does not hold, which prove that T and T_s have to share at least one edge, and it is w(s, v) in MST T.

If there is a weight with 0 cost, the situation is alike. You can suppose the two vertex which w(a,b) = 0 are the same vertex, and remove one of them. The proof works when weights are non-negative.

when some weights are negative and w(s, p) > w(s ,v), that is, w(p ,v) <0, w(s, v) >= path(s->p->v) can't make w(s, p) < w(s, v).But in MST T, w(s, v) should also not exist,because path(s->p->v) makes s to v with less cost, replace w(s, v) in T with w(s, p) and w(p, v) if necessary makes a a less minimum spanning tree T '. Still contradiciton.

Photoplay