[Solved] Homwork 6

Compute the reflexive closure and then the transitive closure of the relation below. Showthe matrix after each pass of the outermost for loop.[0 1 0 0 01 0 0 0 11 0 0 1 00 0 0 1 01 0 0 0 1]

2. Draw the directed graph defined by the adjacency matrix in problem 1. Show itscondensation graph. Reorder the vertices in the rows and columns of the reflexivetransitiveclosure matrix from problem 1 in any topological order defined by thecondensation graph. Examine the resulting matrix and describe how the stronglyconnectedcomponents are reflected in that matrix.3. Modify Floyd’s all-pairs shortest paths algorithm so that k is varied in the innermost loopinstead of the outermost. Consider the following weighted graph:V = {A, B, C, D} and E = {AB, BC, CD} with the weight of each edge being 1.Execute the modified algorithm on this matrix associated with this graph. Is the result thesame as what Floyd’s algorithm would produce? Explain.4. Use Floyd’s algorithm to compute the distance matrix for the digraph whose edge-weightmatrix is:[0 2 4 33 0  35  0 −3 −1 4 0]