EXERCISE 6.2.3: Inferring information about a graph from matrices of graph powers. A directed graph G...

 

Transcribed Image Text:

EXERCISE 6.2.3: Inferring information about a graph from matrices of graph powers. A directed graph G has 5 vertices, numbered 1 through 5. The 5x5 matrix A is the adjacency matrix for G. The matrices A and A3 are given below. 0 1 000 10000 0 0 1 00 0 1 00 0 A = 1 0 00 0 = 0 0 1 0 0 1 0 0 1 0 0 1 1 0 1 1 1 10 10 0 110 Use the information given to answer the questions about the graph G. (a) Which vertices can reach vertex 2 by a walk of length 3? (b) What is the out-degree of vertex 4 in the transitive closure of G? (c) Is there a walk of length 4 from vertex 4 to vertex 5 in G? (Hint: A4 = A-A.) (d) Is (2, 2) in the transitive closure of G? (e) Is (5, 3) an edge in G? (f) Is there a closed walk of length 3 in G? Feedback? EXERCISE 6.2.3: Inferring information about a graph from matrices of graph powers. A directed graph G has 5 vertices, numbered 1 through 5. The 5x5 matrix A is the adjacency matrix for G. The matrices A and A3 are given below. 0 1 000 10000 0 0 1 00 0 1 00 0 A = 1 0 00 0 = 0 0 1 0 0 1 0 0 1 0 0 1 1 0 1 1 1 10 10 0 110 Use the information given to answer the questions about the graph G. (a) Which vertices can reach vertex 2 by a walk of length 3? (b) What is the out-degree of vertex 4 in the transitive closure of G? (c) Is there a walk of length 4 from vertex 4 to vertex 5 in G? (Hint: A4 = A-A.) (d) Is (2, 2) in the transitive closure of G? (e) Is (5, 3) an edge in G? (f) Is there a closed walk of length 3 in G? Feedback?