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 0 0 0 1

 1 0 0 0 0

 0 0 1 1 0

0 0 1 0 0

 1 0 1 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 a 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 4 5

 2 0 3 3

 2 0

 −2  −4 0 ]

Show the intermediate matrices after each iteration of the outermost loop.