208 DIRECTED GRAPHS [CHAP. 9
Suppose now that there is a path from vertexvito vertexvjin a graphGwithmvertices. Then there must
be a simple path fromvitovjwhenvi=vj, or there must be a cycle fromvitovjwhenvi=vj. SinceGhas
mvertices, such a simple path must have lengthm−1 or less, or such a cycle must have lengthmor less. This
means that there is a nonzeroijentry in the matrixBm(defined above) whereAis the adjacency matrix ofG.
Accordingly, the path matrixPandBmhave the same nonzero entries. We state this result formally.
Proposition 9.5: LetAbe the adjacency matrix of a graphGwithmvertices. Then the path matrixPandBm
have the same nonzero entries where
Bm=A+A^2 +A^3 +···+AmRecall that a directed graphGis said to bestrongly connectedif, for any pair of verticesuandvinG, there
is a path fromutovand fromvtou. Accordingly,Gis strongly connected if and only if the path matrixPofG
has no zero entries. This fact together with Proposition 9.5 gives the following result.
Proposition 9.6: LetAbe the adjacency matrix of a graphGwithmvertices. ThenGis strongly connected if
and only ifBmhas no zero entries where
Bm=A+A^2 +A^3 +···+AmEXAMPLE 9.8 Consider the graphGand its adjacency matrixAappearing in Fig. 9-4. HereGhasm= 4
vertices. Adding the matrixAand matricesA^2 ,A^3 ,A^4 in Example 9.7, we obtain the following matrixB 4 and
also path (reachability) matrixPby replacing the nonzero entries inB 4 by 1:
B 4 =⎡
⎢
⎢
⎣4034
110711
7047
7047⎤
⎥
⎥
⎦ and P=⎡
⎢
⎢
⎣1011
1011
1011
1011⎤
⎥
⎥
⎦Examining the matrixB 4 orP, we see zero entries; henceGis not strongly connected. In particular, we see that
the vertexv 2 is not reachable from any of the other vertices.
Remark: The adjacency matrixAand the path matrixPof a graphGmay be viewed as logical (Boolean)
matrices where 0 represents “false” and 1 represents “true.” Thus the logical operations of∧(AND) and
∨(OR) may be applied to the entries ofAandPwhere these operations, used in the next section, are defined
in Fig. 9-5.
Fig. 9-5Transitive Closure and the Path Matrix
LetRbe a relation on a finite setVwithmelements. As noted above, the relationRmay be identified with
the simple directed graphG=G(V, R). We note that the composition relationR^2 =R×Rconsists of all pairs
(u, v)such that there is a path of length 2 fromutov. Similarly:
RK={(u, v)|there is a path of lengthKfromutov}.