Indicate a minimum spanning tree of the below graph.
Problem R5.2
Suppose we were to execute Prim's algorithm beginning at the
center bottom vertex. In what order would edges be added to
the minimum spanning tree?
4, 5, 1, 2
Problem R5.3
Suppose we were to execute Kruskal's algorithm beginning at the
center bottom vertex. In what order would edges be added to
the minimum spanning tree?
1, 2, 4, 5
Problem R5.4
Give an example of an undirected, weighted graph for which there is a pair
of vertices s and t where the shortest
path from s to t does
not lie within the graph's minimum spanning tree. Justify your
answer.
In the above graph, there is just one minimum spanning tree,
which includes the edges labeled 2 and 3. However, the shortest
path from s to t is to take
the edge of length 4, which is not included
in the minimum spanning tree.
printable version
