Say, we have a graph G represented by an adjacency matrix A.
Adjacency Matrix A
A = 0 1 1 0
1 0 1 1
1 1 0 1
0 1 1 0
It is said that A^n[i][j]
equals the
number of distinct walks of length [![n][2]][2] which start at vertex i
and end at vertex j
A^n = A*A*A...n times
Testing for n = 2
A^2 = 2 1 1 2
1 3 2 1
1 2 3 1
2 1 1 2
This says that, the number of paths of length 2, between vertex 0 and 0 is 2, which is indeed correct. The paths are 0-1-0
and 0-2-0
Testing for n = 3
A^3 = 2 5 5 2
5 4 5 2
5 5 4 5
2 5 5 2
This says that, the number of paths of length 3, between vertex 0 and 1 is 5. Are these paths 0-0-2-1
, 0-1-2-1
, 0-1-3-1
,0-2-0-1
, 0-2-1-1
and `0-2-3-1'
I would like to know the idea behind this method, and how it's working.
Best Answer
Just check the matrix multiplication formula for an individual entry:
$${A^n}_{ij} = \sum_{k=1}^v (A^{n-1})_{ik}A_{kj} $$
This translates into something like number paths from $i$ to $j$ is the sum of paths $i$ to $k$ and $k$ to $j$.