Given the following graph G find the following the adjacency

Given the following graph G, find the following. the adjacency matrix for G the number of paths of length 3 from u to v the (strongly) connected components of G

Solution

Adjacency Matrix for graph G:

U

V

W

X

Y

Z

U

1

1

0

0

0

1

V

1

1

1

0

1

0

W

0

0

1

1

0

0

X

0

0

1

0

0

0

Y

0

0

0

1

1

1

Z

0

1

0

0

1

0

Number of paths of length 3 from u to v = 2

1. u --> u --> u ---> v

2. u --> u --> z ----> v

Strongly connected components of graph G:

u,v,y,z ---> these components can reach to any other vertices unlike w and x (which cannot reach vertex \'v\' and

y\')

Thank you. Have a nice day!!

	U	V	W	X	Y	Z
U	1	1	0	0	0	1
V	1	1	1	0	1	0
W	0	0	1	1	0	0
X	0	0	1	0	0	0
Y	0	0	0	1	1	1
Z	0	1	0	0	1	0