What is the formula to compute the transitive closure of a graph? Options tij(k) = tij(k-1) AND (tik(k-1) OR tkj(k-1)) tij(k) = tij(k-1) OR (tik(k-1) AND tkj(k-1)) tij(k) = tij(k-1) AND (tik(k-1) AND tkj(k-1)) tij(k) = tij(k-1) OR (tik(k-1) OR tkj(k-1))

Use Warshall's algorithm to compute the transitive closure of the graph with the following adjacency matrix: 0 0 1 1 1 0 0 1 0 0 0 0 0 1 1 0 Choose the correct values for the unknown variables after each of the four steps for the algorithm. After the first step: 0 0 1 1 1 a1 b1 1 0 0 0 0 c1 1 1 0 [ Select ] After the second step: 0 0 1 1 1 a2 b2 1 0 0 0 0 c2 1 1 1 [ Select ] After the third step: 0 0 1 1 1 a3 b3 1 0 0 0 0 c3 1 1 1 [ Select ] After the fourth and final step: 1 1 1 1 1 a4 b4 1 0 0 0 0 c4 1 1 1 [ Select ]

Dynamic Programming: Warshall’s algorithmApply Warshall’s algorithm to find the transitive closure of the digraph defined by thefollowing adjacency matrix:[[0,0,0,1],[0,0,1,0],[0,0,0,1],[0,0,0,0]]

If a graph has 'n' vertices, what is the maximum size of the matrix required to represent its transitive closure using the Warshall algorithm?

Which of the following pseudocode correctly represents the initialization step of the Warshall algorithm for finding the transitive closure of a graph?Marks : 1Negative Marks : 0Answer hereProcedure WarshallInit(Graph G):  For each vertex v in G:    For each vertex u in G:      If u is adjacent to v:        Set distance[u][v] to 1      Else:        Set distance[u][v] to 0Procedure WarshallInit(Graph G):  For each vertex u in G:    For each vertex v in G:      If u is adjacent to v:        Set distance[u][v] to 1      Else:        Set distance[u][v] to infinityProcedure WarshallInit(Graph G):  For each vertex v in G:    For each vertex u in G:      If u is adjacent to v:        Set distance[v][u] to 0      Else:        Set distance[v][u] to 0Procedure WarshallInit(Graph G):  For each vertex u in G:    For each vertex v in G:      If u is adjacent to v:        Set distance[v][u] to 1      Else:        Set distance[v][u] to infinity

The Warshall algorithm uses ____ nested loops to compute the transitive closure.