Review 5: Minimum spanning trees: Questions

R5.1.

Indicate a minimum spanning tree of the below graph.

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?

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?

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.

Review 5: Minimum spanning trees: Solutions

R5.1.
R5.2.
4, 5, 1, 2
R5.3.
1, 2, 4, 5
R5.4.

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.