Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

In a graph, if I expand a vertex to a minimum spanning tree, does this entail that the path(s) obtained by walking from the start vertex to any other vertex along the tree are minimal? Thanks

share|improve this question
2  
No, as a counterexample take a triangle with weights $4, 5, 6$ on edges. –  Levon Haykazyan Jun 1 '12 at 18:56
    
Thanks but in your example, the path from any vertex that we choose to be the start vertex to one of the other 2 vertices is still the minimal between those 2 though. That's the property of triangle inequality, isn't it? –  cody Jun 1 '12 at 19:07
    
I can't understand your comment. Consider the graph with vertices $a, b, c$ and edges $ab, bc, ca$ with assigned weights $4, 5, 6$. Then the spanning tree with minimal weight is $ab, bc$, but the shortest put from $a$ to $c$ is $ac$. Is this not correct? –  Levon Haykazyan Jun 1 '12 at 19:14
    
My question is: if b is the first vertex we use to create the MST, is ba and bc the minimum cost path from b to any other vertex? The first vertex is important in my question because we may have different MST's if we start from different vertex. –  cody Jun 1 '12 at 19:25
    
So this is an example showing that your assertion as stated is not correct, because you may be starting from the vertex $a$. –  Levon Haykazyan Jun 1 '12 at 19:31

1 Answer 1

In general, one should not expect an MST to provide the shortest paths, even from a vertex used first in the construction of the MST. In addition to the counterexample of a triangle with weights 4,5,6 on edges, given by Levon Haykazyan, consider this example from Wikipedia:

MST example

The nearly-horizontal edge with weight $9$ will not be included in any MST, because the edge with weight $8$ is the better way to connect the cluster on the left to the rest of the graph. Traveling along the MST between the endpoints of this weight 9 edge takes at least 10 units.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.