Reputation: 25842
Here is an exercise:
Either prove the following or give a counterexample:
(a) Is the path between a pair of vertices in a minimum spanning tree of an undirected graph necessarily the shortest (minimum weight) path?
(b) Suppose that the minimum spanning tree of the graph is unique. Is the path between a pair of vertices in a minimum spanning tree of an undirected graph necessarily the shortest (minimum weight) path?
My Answer is
(a)
No, for example, for graph 0, 1, 2, 0-1 is 4, 1-2 is 2, 2-0 is 5, then 0-2’s true shortest path is 5, but the mst is 0-1-2, in mst, 0-2 is 6
(b)
My problem comes into this (b).
I don't understand how whether the MST is unique
can affect the shortest path.
First, my understanding is that when the weights of edges are not distinct, multiple MST may exist at the same time, right?
Second, even if MST is unique, the answer of (a) above still applies for (b), right?
Upvotes: 17
Views: 23989
Reputation: 373
a very simple visualization would be:
I guess that the uniqueness of MSP means that there is only 1 MSP MSP in a graph. So:
First) Yes, if the weights of edges are not distinct, multiple MST may exist at the same time. In case of our graph, another possible MSP would include arc D-C instead of A-B (as an example).
Second) The uniqueness of MST does not influence the answer for a). As an example:
Upvotes: 1
Reputation: 5619
So lets take a look at a very simple graph:
(A)---2----(B)----2---(C)
\ /
---------3----------
The minimum spanning tree for this graph consists of the two edges A-B
and B-C
. No other set of edges form a minimum spanning tree.
But of course, the shortest path from A
to C
is A-C
, which does not exist in the MST.
EDIT
So to answer part (b) the answer is no, because there is a shorter path that exists that is not in the MST.
Upvotes: 25
Reputation: 1
Isn't the MST related to the start node?!
Then he is trying to get the shortest path from the MST start node. Therefore, yes, the shortest path is given by the MST starting from A
!
Upvotes: 0
Reputation: 2579
Regarding (a), I agree.
Regarding (b), for some graphs, there may be more minimal spanning trees with the same weight. Consider a circle C3 with vertices a,b,c; weights a->b=1, b->c=2, a->c=2. This graph has two MSTs, {a-b-c} and {c-a-b}.
Nevertheless, your counterexample still holds, because the MST is unique there.
Upvotes: 6