1
$\begingroup$

I have a feeling this might be wrong an I'm looking for a counter example, however, I couldn't find one yet.. can anyone guide me in the right direction?

$\endgroup$
  • $\begingroup$ What's the definition of an MST in an unweighted graph? $\endgroup$ – lox Jun 24 '19 at 21:33
  • $\begingroup$ Perhaps the following question and the examples given there are helpful: Minimum spanning tree vs Shortest path. $\endgroup$ – Hendrik Jan Jun 24 '19 at 22:07
  • $\begingroup$ @IOX: I think you can just assume it's like a weighted graph but all edges have the same weight (or just say have weight 1). Hendrik: thanks! $\endgroup$ – user106782 Jun 24 '19 at 22:15
  • $\begingroup$ if all edges have the same weight, then any tree has a weight of $w(V-1)$, which makes any tree MST. I think you meant to ask the question with a weighted graph. In which case the answer is no. $\endgroup$ – lox Jun 24 '19 at 22:44
  • $\begingroup$ Since every tree in an unweighted graph is an MST, your question asks whether every tree is a shortest path tree. It looks like this is true if and only if the given graph is acyclic. $\endgroup$ – mo2019 Jun 29 '19 at 12:06
2
$\begingroup$

Counter example: V={a,b,c,d}, E={(a,b), (a,c), (a,d), (b,c)}. A MST of this graph, rooted at a, could be: {(a,b), (a,d), (b,c)}. But this is not a SPT because the path a->c is of length 2 instead of 1 (a and c are directly connected in the original graph).

$\endgroup$
0
$\begingroup$

Shortest-path tree is defined for a graph and a root vertex.

Edit: My previous example was for a weighted graph, but still you can find counter-examples by choosing the root vertex carefully.

$\endgroup$
  • $\begingroup$ Does this make sense: I have a graph G = (V,E) with V = {A,B,C} and E = {(A,B), (B,C), (A,C)} and say my MST G' has edges {(C,A), (C,B)} it's not a SPT when I set the root of the SPT at A. Therefore not every MST is a SPT. $\endgroup$ – user106782 Jun 24 '19 at 21:36
  • $\begingroup$ Seems right to me $\endgroup$ – Shahaf Finder Jun 24 '19 at 21:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy