CODEWITHSUNDEEP
algorithmmathgraphshortest-pathminimum-spanning-tree
Spartacus
Spartacus

Reputation: 131

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

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 Ts be a shortest-path tree for some node s. Are T and Ts 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?

Upvotes: 12

Views: 7132

Answers (2)

vvy
vvy

Reputation: 2073

Proof To vertex s and its shortest-path tree Ts, the wedge in MST T is w(s, v) ,and suppose it doesn't exist in Ts . 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 Ts 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.

Upvotes: 4

templatetypedef
templatetypedef

Reputation: 372664

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!

Upvotes: 6

Related Questions