CHAP. 9] DIRECTED GRAPHS 207
Then the entries ofAwill be nonnegative integers. Conversely, everym×mmatrixAwith nonnegative integer
entries uniquely defines a directed graph withmvertices.
EXAMPLE 9.6 LetGbe the directed graph in Fig. 9-4(a) with verticesv 1 ,v 2 ,v 3 ,v 4. Then the adjacency matrix
AofGappears in Fig. 9-4(b). Note that the number of 1’s inAis equal to the number (eight) of edges.
Fig. 9-4
Consider the powersA,A^2 ,A^3 ,... of the adjacency matrixA=[aij]of a graphG. LetaK(i, j )=theijentry in the matrixAKNote thata 1 (i, j )=aijgives the number of paths of length 1 from vertexvito vertexvj. One can show that
a 2 (i, j )gives the number of paths of length 2 fromvitovj. In fact, we prove in Problem 9.17 the following
general result.
Proposition 9.4: LetAbe the adjacency matrix of a graphG. ThenaK(i, j ), theijentry in the matrixAK, gives
the number of paths of lengthKfromvitovj.
EXAMPLE 9.7 Consider again the graphGand its adjacency matrixAappearing in Fig. 9-4. The powersA^2 ,
A^3 , andA^4 ofAfollow:
A^2 =⎡
⎢
⎢
⎣1010
2012
1011
1002⎤
⎥
⎥
⎦,A(^3) =
⎡
⎢
⎢
⎣
1002
3023
2012
2021
⎤
⎥
⎥
⎦,A
(^4) =
⎡
⎢
⎢
⎣
2021
5035
3023
3014
⎤
⎥
⎥
⎦
Observe thata 2 (4, 1)=1, so there is a path of length 2 fromv 4 tov 1. Also,a 3 (2, 3)=2, so there are two paths
of length 3 fromv 2 tov 3 ; anda 4 (2, 4)=5, so there are five paths of length 4 fromv 2 tov 4.
Remark: LetAbe the adjacency matrix of a graphG, and letBrbe the matrix defined by:
Br=A+A^2 +A^3 +···+Ar
Then theijentry of the matrixBrgives the number of paths of lengthror less from vertexvito vertexvj.
Path Matrix
LetG=G(V , E)be a simple directed graph withmverticesv 1 ,v 2 ,...,vm. Thepath matrixorreachability
matrixofGis them-square matrixP=[pij]defined as follows:
pij=
{
1 if there is a path from tovitovj
0 otherwise
(The path matrixPmay be viewed as the transitive closure of the relationEonV.)