DM-Graphs-Q8

A represents an adjacency matrix of Graph G

$\begin{bmatrix} 0& 1&0&0\\ 1 & 0 & 1 & 1\\ 0 & 1 & 0 & 0\\ 0 & 1 & 0 & 0 \end{bmatrix}$

The number of paths of length 8  from vertex 1 to vertex 4.

asked Jul 12, 2019 1 flag
reshown Jul 13, 2019

Answer is 0   (I am not sure plz suggest)

answered Jul 13, 2019 by (1,080 points)
find A^8 matrix and entry (1,4) in A^8 is required answer.
answer should be 27 A^8 have to computed by taking adjacent matrix
Is there any shortcut to find the same? or do we need to calculate by multiplying it 8 times
how is A^8 soln of this question?
A^8 could be calculated by cayley hamilton theorem ,but not getting an idea why A^8 is soln of this question
In matrix a^n each (i,j) entry gives the no of paths of length n from i to j.
Yes, only 3 multiplications are necessary. A^2 = A*A, then  A^4 = A^2*A^2 then A^8 = A^4*A^4.
bro it given only simple matrix .so why you mutiply 8 times .i think ans should be 0 plz give valid reason

I feel like the biggest idiot...

We have to choose a path of exactly 8 edges i.e 9 vertices will be in the path.

First vertex must be 1, and Last vertex(i.e 9th vertex on the path) must be 4

Second vertex must be 2(as  there is only one path from 1 i.e towards 2)

Third vertex could be anything(either 1 or 3 or 4 ie. total of 3 choices here)

Fourth vertex must be 2(there is only one path from 1 or 3 or 4 i.e toward 2)

Fifth vertex could be anything(i.e either 1 or 3 or 4 => total of 3 choices here)

Sixth vertex must be 2(same reason as for the fourth vertex)

7th vertex could be anything(1 or 3 or 4 so again 3 choices)

8th vertex must be 2

we've already defined 9th(the last vertex)

Now the path would look like:

(1)->(2)->(3 or 4 or 5)->(2)->(3 or 4 or 5)->(2)->(3 or 4 or 5)->(2)->(4)

so, simply we have 3*3*3 path = 27

I forgot to multiply by the last 3 and got the wrong answer;<

answered Dec 14, 2019 by (990 points)