CMSC451 Homework 5 Solution

1. Execute Prim’s minimum spanning tree algorithm by hand on the graph below showing how the data structures evolve specifically indicating when the distance from a fringe vertex to the tree is updated. Clearly indicate which edges become part of the minimum spanning tree and in which order. Start at vertex A.

2. Execute Kruskal’s algorithm on the weighted tree shown below. Assume that edges of equal weight will be in the priority queue in alphabetical order. Clearly show what happens each time an edge is removed from the priority queue and how the dynamic equivalence relation changes on each step and show the final minimum spanning tree that is generated.

3. Give an example of a weighted graph for which the minimum spanning tree is unique. Indicate what the minimum spanning tree is for that graph. Give another example of a weighted graph that has more than one minimum spanning tree. Show two different minimum spanning trees for that graph. What determines whether a graph has more than one minimum spanning tree?
4. Given the following adjacency lists (with edge weights in parentheses) for a directed graph:
A: B(5), C(3), D(1)
B: C(1), D(3)
C: B(3), D(7), E(1)
D: A(6), C(3)
E: F(5)
F: D(3), A(4)
Execute Dijkstra’s shortest-path algorithm by hand on this graph, showing how the data structures evolve, with A as the starting vertex. Clearly indicate which edges become part of the shortest path and in which order.

Grading Rubric
Problem Meets Does Not Meet
Problem 1 10 points 0 points

Indicated when the distance from a
fringe vertex to the tree was updated (3) Did not indicate when the distance from a fringe vertex to the tree was updated (0)
Indicated which edges became part of the minimum spanning tree and in which order (3) Did not indicate which edges became part of the minimum spanning tree and in which order (0)
Provided the correct final minimum spanning tree (4) Did not provide the correct final minimum spanning tree (0)
Problem 2 10 points 0 points

Showed what happened each time an edge was removed from the priority queue (3) Did not show what happened each time an edge was removed from the priority queue (0)
Showed how the dynamic equivalence relation changed on each step (3) Did not show how the dynamic equivalence relation changed on each step (0)
Provided the correct final minimum spanning tree (4) Did not provide the correct final minimum spanning tree (0)
Problem 3 10 points 0 points

Provided a correct example of a weighted graph for which the minimum spanning tree is unique (2) Did not provide a correct example of a weighted graph for which the minimum spanning tree is unique (0)
Provided the correct unique minimum spanning tree for that graph (2) Did not provide the correct unique
minimum spanning tree for that graph
(0)
Provided a correct example of a weighted graph that has more than one minimum spanning tree (2) Did not provide a correct example of a weighted graph that has more than one minimum spanning tree (0)
Provided two correct distinct minimum spanning trees for that graph (2) Did not provide two correct distinct
minimum spanning trees for that graph
(0)
Correctly explained what determines whether a graph has more than one minimum spanning tree (2) Did not correctly explain what determines whether a graph has more than one minimum spanning tree (0)

Problem 4 10 points 0 points

Clearly indicated which edges became part of the shortest path and in which order (5) Did not clearly indicate which edges became part of the shortest path and
in which order (0)
Provided correct final shortest path tree (5) Did not provide correct final shortest path tree (0)