## Description

CMSC 451 Homework 5

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.

A B G

F I H C

E D

2

2 2

2 1

1 3 3 4

5 4 6

6 7

8

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)