Suppose we are given an unweighted, directed graph G with n vertices (labelled 1

Question

Suppose we are given an unweighted, directed graph G with n vertices (labelled 1 to n), and let M be the n × n adjacency matrix for G (that is, M (i,j) = 1 if directed edge (1J) is in G and 0 otherwise). a. Let the product of M with itself (M2) be defined, for 1 S i,j Sn, as follows: 4. 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? 40 b. Suppose M4 is the product of M2 with itself. What do the entries of M+ signify? What about M for any 1 sksn?

Explanation / Answer

a) M2(i,j) = 1 means that in the original graph with adjacency matrix M there was path between i and j with exactly two edges.

M2(i,j) = 0 means that in the original graph with adjacency matrix M there was NO path between i and j with exactly two edges.

b) M4(i,j)=1  means that in the original graph with adjacency matrix M there was path between i and j with exactly four edges.

Similarly for M4(i,j)=0

Mk(i,j)=1  means that in the original graph with adjacency matrix M there was path between i and j with exactly k edges.

Similarly for Mk(i,j)=0.

Related Questions

Navigate

• Browse (All)
• Browse S
• Subjects

---

---

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