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
Does a Minimum Spanning Tree entail minimum cost between 2 vertices?
0
$\begingroup$
algorithms
graph-theory
-
2No, as a counterexample take a triangle with weights $4, 5, 6$ on edges. – 2012-06-01
-
0Thanks 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? – 2012-06-01
-
0I 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? – 2012-06-01
-
0My 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. – 2012-06-01
-
0So this is an example showing that your assertion as stated is not correct, because you may be starting from the vertex $a$. – 2012-06-01
-
0Oh, I see. Thank you. – 2012-06-01