Mathematics for Computer Science

Chapter 9 Directed graphs & Partial Orders324

For example, letHbe the 4-node graph shown in Figure 9.1. Its adjacency matrix,
AH, is the 4  4 matrix:

AHD

a b c d

a 0 1 0 1

b 0 0 1 1

c 0 1 0 0

d 0 0 1 0

A payoff of this representation is that we can use matrix powers to count numbers
of walks between vertices. For example, there are two length two walks between
verticesaandcin the graphH:

aha!bibhb!cic

aha!did hd!cic

and these are the only length two walks fromatoc. Also, there is exactly one
length two walk frombtocand exactly one length two walk fromctocand from
dtob, and these are the only length two walks inH. It turns out we could have
read these counts from the entries in the matrix.AH/^2 :

.AH/^2 D

a b c d

a 0 0 2 1

b 0 1 1 0

c 0 0 1 1

d 0 1 0 0

More generally, the matrix.AG/kprovides a count of the number of lengthk
walks between vertices in any digraph,G, as we’ll now explain.

Definition 9.3.1.The length-kwalk counting matrixfor ann-vertex graphGis the
nnmatrixCsuch that

CuvWWDthe number of length-kwalks fromutov: (9.4)

Notice that the adjacency matrixAGis the length- 1 walk counting matrix forG,
and that.AG/^0 , which by convention is the identity matrix, is the length-0 walk
counting matrix.

Theorem 9.3.2.IfCis the length-kwalk counting matrix for a graphG, andD
is the length-mwalk counting matrix, thenCDis the lengthkCmwalk counting
matrix forG.