Let A be the adjacency matrix of a directed graph G = (V, E), where A(i, j) = 1

Question

Let A be the adjacency matrix of a directed graph G = (V, E), where A(i, j) = 1 if E and A(i, j) = 0 otherwise. Define the transitive closure, A^+, of A to be a matrix with the property A^+(i, j) = 1 iff G has a directed path, containing at least one edge, from vertex i to vertex j. A^+ (i, j) = 0 otherwise. The reflexive transitive closure, A*, is a matrix with the property A*(i, j) = 1 iff G has a path, containing zero or more edges, from i to j. A*(i, j) = 0 otherwise. Obtain A, A^+ and A* for the above directed graph. Let A^k (i, j) = 1 iff there is a path with zero or more edges from i to j going through no vertex of index greater than k. Define A^0. Obtain a recurrence definition between A^k and A^k - 1 using the logical operators or and and rather than min and +. Write an algorithm, using the recurrence of (c), to find A*. What is the time complexity of your algorithm?

Explanation / Answer

a)

b)

Adjecency matrix it self is the A0

c)

Recurrence using min and +:

Recurrence using logical operators or and and:

(or (and ) d)

d)

The algorithm to find A*:

Algorithm A* (A,n)

//A is the adjacency matrix of agraph G with n vertices;

// A consists the Boolean values 0 or 1.

//A0=A

{

              for k:=1 to n do

                        for i:=1to n do

                                    for j:=1 to n do

                                                   (

}

The time complexity of the above algorithm is

Related Questions

Navigate

• Browse (All)
• Browse L
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.