Suppose we are given a directed graph G with n vertices, and let M be the n×n adjacency matrix corresponding to G.

a. Let the product of M with itself (M²) be defined, for 1‰¤i, j ‰¤n, as follows:

where €œŠ•€ is the boolean or operator and €œŠ™€ is boolean and. Given this definition, what does M²(i, j) = 1 imply about the vertices i and j? What if M²(i, j) = 0?

b. Suppose M⁴ is the product of M² with itself. What do the entries of M⁴ signify? How about the entries of M⁵ = (M⁴)(M)? In general, what information is contained in the matrix M^p?

c. Now suppose that G is weighted and assume the following:

1: for 1 ‰¤ i ‰¤ n, M(i, i) = 0.

2: for 1 ‰¤ i, j ‰¤ n, M(i, j) = weight(i, j) if (i, j) is in E.

3: for 1 ‰¤ i, j ‰¤ n, M(i, j) = ˆž if (i, j) is not in E.

Also, let M2 be defined, for 1 ‰¤ i, j ‰¤ n, as follows:

M2(i, j) = min{M(i,1)+M(1, j), . . . ,M(i,n)+M(n, j)}.

If M2(i, j) = k, what may we conclude about the relationship between vertices i and j?

Transcribed Image Text:

|M" (i, ) — M(i,1)оM(1,) @...өМ(і, n) о M(п, j),