Algorithm Problems

1.    Chapter 9, problem 9.1, page 446

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.    Chapter 9, problem 9.3, page 447

Use Algorithm 9.2 to compute the transitive closure of the relation A given in Example 9.1. Show the matrix after each pass of the outermost for loop.

Example 9.1 Transitive closure of one relation

For the following A, the transitive closure is R.

Algorithm 9.2. 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

void transtivieClosure(boolean[][] A, int n, boolean [][] R)

   int i, 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]);