4. Suppose we are given an unweighted, directed graph G with n vertices (labelle

Question

4. Suppose we are given an unweighted, directed graph G with n vertices (labelled 1 to n), and let M be the n x n adjacency matrix for G (that is, M(i,j) 1 if directed edge (i, j) is in G and 0 otherwise). a. Let the product of M with itself (M2) be defined, for 1 sijsn, as follows: where "" is the Boolean and operator and"+"is the Boolean or operator. Given this definition what does M2(i,j)- 1 imply about vertices i and j? What if M2(i,j) 0? b. Suppose M4 is the product of M2 with itself. What do the entries of M4 signify? What about M for any 1 s ks n?

Explanation / Answer

Given an Unweighted,directed graph G(n) where n is number of vertices.

M(i,j) is an Adjacency Matrix ,where M(i,j)=1 means there is an edge between vertex i and vertex j.

According to the definition of M2(i,j)

(i)------------>(p)-------------->(j) where p is an itermediate vertex between i and j.

M2(i,j)=1 ,means there is a path between vertex i and vertex j taking one intermediate vertex it can be

any vertex between 1 to n.

M2(i,j)=0 there is no any path between i and j considering only one intermediate vertex.

M4(i,j)=M2(i,j) * M2(i,j) each entries in M4(i,j) signifies that is there a path between vertex i and vertex j taking three intermediate vertices ,where three intermediate vertices can be any subset of length 3 in set(1...n).

(i)------>(n1)-------->(n2)-------->(n3)---------->(j), where n1 to n3 are intermediate vertices.

Each entries in Mk(i,j) signifies that is there a path between vertex i and vertex j taking total k-1 intermediate vertices,where k-1 intermediate vertices can be any subset of length k-1 in set(1...n).

(i)------>(n1)----->(n2)----->(n3)--------->....................------>(n(k-2))-------->(nk-1)------------>(j) where n1 to nk-1 are intermediate k-1 vertices.

Related Questions

Navigate

• Browse (All)
• Browse 4
• Subjects

---

---

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