8.17

(a) Identical MST and shortest-path tree
Let V = {r,a,b,c} and give the undirected edges the following positive weights:
(r,a)=1, (a,b)=2, (b,c)=3.
The graph is already a tree, so it is its own minimum-spanning tree (MST). Because every path from the root r to any other vertex is unique, this same edge set is also the shortest-path spanning tree (SPT) rooted at r.

(b) Very different MST and shortest-path tree (directed)
Take the directed graph
V={s,a,b,c}
E={s→a:1, s→b:1, a→b:1, b→c:1, c→a:1, s→c:100}.
• Minimum-cost arborescence (directed MST) rooted at s:
   {s→a, a→b, b→c} (total cost = 3).
• Shortest-path tree rooted at s:
   {s→a, s→b, b→c} (distances: d(a)=1, d(b)=1, d(c)=2).
Only one edge coincides; two out of three edges are different, so the trees are “very different.”

(c) Can the two trees be completely disjoint?
Yes. Ties in edge weights (or simply working with directed graphs) let the two algorithms pick edge sets with no overlap. For instance, in the directed graph
V={s,a,b}, E={s→a:1, s→b:1, a→b:0, b→a:0}:
• An MST algorithm that breaks ties by first choosing a→b produces the arborescence    {s→a, a→b}.
• A shortest-path algorithm that breaks distance ties in favour of vertex b yields the SPT
   {s→b, b→a}.
These two directed trees share no common edge, so they are completely disjoint.

Back to Chapter 8