Reference no: EM13332119

1- Let G = ( V , E ) be an undirected graph and let R be a relation on V defined by vRw if and only if there exists a path from v to w . (Recall there is a path of length zero from any vertex to itself.)
1. Show that R is an equivalence relation.
2. What are the equivalence classes of this relation?
3. Show that the reachability matrix R for an undirected graph with n vertices can be constructed in 0 ( n 2 )time.

2- compute the transitive closure of the relation A given in Example 9.1. Show the matrix after each pass of the outermost for loop.

Transitive closure of one relation
For the following A,the transitive closure is R.

Warshall's Algorithm
input: A and n, where A is an n X n adjacency matrix
output: R, the n X n transitive closure matrix of A
voidtranstivieClosure(boolean[][] A, int n, boolean [][] R)
inti, j, k;
Copy A into R;
Set all main diagonal entries, r[i][i] to true;
for (k=1; k<=n; k++)
for (i=1; i<=n; i++)
for (j=1; j<=n; j++)
r[i][j] = r[i][j] | (r[i][k] & r[k][j]);