Let n be a positive integer and consider two n x n matrices M and M2....

 

Transcribed Image Text:

Let n be a positive integer and consider two n x n matrices M₁ and M2. The Boolean matrix product of M₁ and M2, denoted by M' = M₁ M2, is the nxn matrix M' in which M'[i, j] is: M'[i, j] = (M₁[1,0] ^ M₂[0, j]) V (M₁[i, 1] ^ M₂[1, j]) VV (M₁[i,n-1] A M₂[n-1, j]). Now consider a directed graph G = (N,E) implemented via the matrix representation M with n = |N|. P3.1. Let M' = MM. What does the value M'[i, j] represent (when is it true and when is it false)? P3.2. Consider paths of length k in graph G. Provide an algorithm that uses the Boolean matrix product operations to compute a matrix Mk such that, for every pair of nodes n, m = N, M [id(n), id (m)] is true if and only if there is a path of length exact-k from node n to node m. Explain why your algorithm is correct and provide the complexity of your algorithm in terms of the number of Boolean matrix product operations used. Hint. One can design an algorithm that performs at-most-log,(k) Boolean matrix product operations. P3.3. The transitive closure of G is a graph G' = (N,&') such that (n, m) e E' if and only if there is a path from node n to node m in graph G. Provide an algorithm that uses the Boolean matrix product operations to compute a matrix M' that represents graph G'. Explain why your algorithm is correct and provide the complexity of your algorithm. Let n be a positive integer and consider two n x n matrices M₁ and M2. The Boolean matrix product of M₁ and M2, denoted by M' = M₁ M2, is the nxn matrix M' in which M'[i, j] is: M'[i, j] = (M₁[1,0] ^ M₂[0, j]) V (M₁[i, 1] ^ M₂[1, j]) VV (M₁[i,n-1] A M₂[n-1, j]). Now consider a directed graph G = (N,E) implemented via the matrix representation M with n = |N|. P3.1. Let M' = MM. What does the value M'[i, j] represent (when is it true and when is it false)? P3.2. Consider paths of length k in graph G. Provide an algorithm that uses the Boolean matrix product operations to compute a matrix Mk such that, for every pair of nodes n, m = N, M [id(n), id (m)] is true if and only if there is a path of length exact-k from node n to node m. Explain why your algorithm is correct and provide the complexity of your algorithm in terms of the number of Boolean matrix product operations used. Hint. One can design an algorithm that performs at-most-log,(k) Boolean matrix product operations. P3.3. The transitive closure of G is a graph G' = (N,&') such that (n, m) e E' if and only if there is a path from node n to node m in graph G. Provide an algorithm that uses the Boolean matrix product operations to compute a matrix M' that represents graph G'. Explain why your algorithm is correct and provide the complexity of your algorithm.