Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit

ASSIGNMENT 3

MATH2301, SEMESTER 2, 2022

(1)  Consider a graph whose adjacency matrix is

A = \J

(              ) .

Find the number of paths of length 4 from 1 to 3.

(2)   (a) Find (without explicit calculation) an example of a 4 × 4 nonzero adjacency matrix such that all powers of this matrix beyond the 10th power are zero. Justify briefly.

(b)  Show that the 8th power of any such matrix must also be zero.

(c)  Is it true that the cube of any such matrix also has to be zero?

(3)  Draw the graph of the relation R = {(a, b) | 0 ≤ b − a ≤ 2} on the set S = {1, 2, 3, 4}.  Draw the graph of this relation, and also the transitive closure of the graph of this relation. Also write down the adjacency matrices of both graphs (using the drawing, not using Boolean product).

(4) Find the transitive closure of the relation R = {(a, b) | a + b > 3} on the set {1, 2, 3} using Boolean powers of the adjacency matrix.