Page 216 - Advanced engineering mathematics

196 CHAPTER 7 Matrices and Linear Systems

v r
Length 1
Length k
v i v j

FIGURE 7.2 Constructing v i − v j
walks of length k + 1.

with this sum taken over all points v r adjacent to v i .Now a ir =1if v r is adjacent to v i , and
0 otherwise. Further, by assumption, the number of distinct v r − v j walks of length k is the
k
k
r, j-element of A . Denote A = B =[b ij ]. Then, for r = 1,··· ,n,
a ir b rj = 0if v r is not adjacent to v i
and

a ir b rj =
the number of distinct v i − v j walks of length k + 1if v r is adjacent to v i .
Therefore, the number of v i − v j walks of length k + 1is

a i1 b 1 j + a i2 b 2 j + ··· + a in b nj
and this is the i, j-element of AB, which is A k+1 .

EXAMPLE 7.8
The adjacency matrix of the graph of Figure 7.3 is
⎛ ⎞
01000100
10100011
⎜ ⎟
⎜ ⎟
01010000
⎜ ⎟
⎜ ⎟
00101111
⎜ ⎟
A = ⎜ ⎟ .
00010110
⎜ ⎟
⎜ ⎟
10011000
⎜ ⎟
⎜ ⎟
⎝ 01011001 ⎠
01010010
v 3
v 2
v 8
v 1
v 4
v 7
v 6
v 5

FIGURE 7.3 Graph of Example 7.8.

Copyright 2010 Cengage Learning. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part. Due to electronic rights, some third party content may be suppressed from the eBook and/or eChapter(s).
Editorial review has deemed that any suppressed content does not materially affect the overall learning experience. Cengage Learning reserves the right to remove additional content at any time if subsequent rights restrictions require it.

October 14, 2010 14:23 THM/NEIL Page-196 27410_07_ch07_p187-246