CMSC 451 UMUC Programming Application of A Graph Discussion

Give an example of an application of a graph, in which the minimumspanning tree would be of importance. Describe what the vertices,
edges and edge weights of the graph represent. Explain why finding a
minimum spanning tree for such a graph would be important.
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.
2
3
A
7
5
6
4
G
3
1
F
B
I
4
H
8
2
6
E
C
2
2
1
D
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
Problem 1
Problem 2
Problem 3
Meets
10 points
Does Not Meet
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)
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)
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)
CMSC 451 Homework 6
1. Using Warshall’s algorithm, compute the reflexive-transitive closure of the relation below.
Show the matrix after the reflexive closure and then after each pass of the outermost for loop
that computes the transitive closure.
0
1
0
0
[1
0
0
0
0
0
0
0
1
1
1
0
0
1
0
0
1
0
0
0
1]
2. Using the matrix in the previous problem show the final result of executing Floyd’s
algorithm on that matrix to produce a matrix containing path lengths.
3. Show the graph that corresponds to the matrix in the first problem assuming the rows and
columns correspond to the vertices a, b, c, d and e. Show its condensation graph, renaming its
vertices. Determine any topological order of that graph and create an adjacency matrix with
the vertices ordered in that topological order. Finally compute the reflexive-transitive closure
of that matrix. What characteristic of that matrix indicates that it defines a total order?
4. Using Floyd’s algorithm, compute the distance matrix for the weight directed graph defined
by the following matrix:
0
2
4
0
2

5
3 3
[
]

0 
−2  −4 0
Show the intermediate matrices after each iteration of the outermost loop.
Grading Rubric
Problem
Problem 1
Meets
10 points
Does Not Meet
0 points
Showed the correct matrix after the
reflexive closure (2)
Did not show the correct matrix after
the reflexive closure (0)
Showed the correct matrices after each
pass of the outermost for loop that
computes the transitive closure (8)
Did not show the correct matrices after
each pass of the outermost for loop
that computes the transitive closure (0)
Problem 2
Problem 3
Problem 4
10 points
0 points
Showed the correct final result of
executing Floyd’s algorithm on that
matrix to produce a matrix containing
path lengths (10)
Did not show the correct final result of
executing Floyd’s algorithm on that
matrix to produce a matrix containing
path lengths (0)
10 points
0 points
Showed the correct graph that
corresponds to the matrix in the first
problem assuming vertices a, b, c, d
and e (1)
Did not show the correct graph that
corresponds to the matrix in the first
problem assuming vertices a, b, c, d
and e (0)
Showed its correct condensation
graph, renaming its vertices (2)
Did not show its correct condensation
graph, renaming its vertices (0)
Determined a correct topological order
of that graph (2)
Did not determine a correct topological
order of that graph (0)
Created a correct adjacency matrix
with the vertices ordered in that
topological order (1)
Did not create a correct adjacency
matrix with the vertices ordered in that
topological order (0)
Correctly computed the reflexivetransitive closure of that matrix (2)
Correctly explained what characteristic
of that matrix indicates that it defines a
total order (2)
Did not correctly compute the
reflexive-transitive closure of that
matrix (0)
Did not correctly explain what
characteristic of that matrix indicates
that it defines a total order (0)
10 points
0 points
Showed the correct intermediate
matrices after each iteration of the
outermost loop using Floyd’s algorithm
(7)
Did not show the correct intermediate
matrices after each iteration of the
outermost loop using Floyd’s algorithm
(0)
Showed the correct final matrix after
executing Floyd’s algorithm (3)
Did not show the correct final matrix
after executing Floyd’s algorithm (0)
Give an example of an application of a graph, in which the minimum
spanning tree would be of importance. Describe what the vertices,
edges and edge weights of the graph represent. Explain why finding a
minimum spanning tree for such a graph would be important.
Give an example of an application of a graph, in which determining all pairs shortest paths
would be of importance. Describe what the vertices, edges and edge weights of the graph
represent. Explain the significance of the shortest path for such a graph and why it would be
important.