Description

2 attachmentsSlide 1 of 2attachment_1attachment_1attachment_2attachment_2

Unformatted Attachment Preview

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 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.

Purchase answer to see full

attachment

Explanation & Answer:

4 pages

User generated content is uploaded by users for the purposes of learning and should be used following Studypool’s honor code & terms of service.