Answered You can hire a professional tutor to get the answer.
CMSC 451 Homework 6 1. Using Warshall's algorithm, compute the reflexive-transitive closure of the relation below.
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.
