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?
$\begingroup$
$\endgroup$
5
-
$\begingroup$ What's the definition of an MST in an unweighted graph? $\endgroup$– loxJun 24, 2019 at 21:33
-
$\begingroup$ Perhaps the following question and the examples given there are helpful: Minimum spanning tree vs Shortest path. $\endgroup$– Hendrik JanJun 24, 2019 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$– user106782Jun 24, 2019 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$– loxJun 24, 2019 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$– mo2019Jun 29, 2019 at 12:06
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
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).
$\begingroup$
$\endgroup$
2
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.
-
$\begingroup$ Does this make sense: I have a graph
G = (V,E)withV = {A,B,C}andE = {(A,B), (B,C), (A,C)}and say my MSTG'has edges{(C,A), (C,B)}it's not a SPT when I set the root of the SPT atA. Therefore not every MST is a SPT. $\endgroup$– user106782Jun 24, 2019 at 21:36 -