224 DIRECTED GRAPHS [CHAP. 9
(a) Find the adjacency matrixAof the graphGand the powersA^2 ,A^3 ,A^4.
(b) Find the path matrixPofGusing the powers ofA.IsGstrongly connected?(a) The vertices are normally ordered according to the way they appear in memory; that is, we assumev 1 =X,v 2 =Y,
v 3 =Z,v 4 =W. The adjacency matrixA=[aij]is obtained by settingaij=1 if there is an edge fromvitovj;
and 0 otherwise. The matrixAand its powers follow:A=⎡
⎢⎢
⎣0111
0001
0101
0010⎤
⎥⎥
⎦,A(^2) =
⎡
⎢⎢
⎣
0112
0010
0011
0101
⎤
⎥⎥
⎦,A
(^3) =
⎡
⎢⎢
⎣
0122
0101
0111
0011
⎤
⎥⎥
⎦,A
(^4) =
⎡
⎢⎢
⎣
0223
0011
0112
0111
⎤
⎥⎥
⎦
(b) SinceGhas 4 vertices, we need only find the matrixB 4 =A+A^2 +A^3 +A^4 , and then the path matrixP=[pij]
is obtained by settingpij=1 whenever there is a nonzero entry in the matrixB 4 , and 0 otherwise. The matrices
B 4 andPfollow:
B 4 =
⎡
⎢⎢
⎣
0568
0123
0335
0235
⎤
⎥⎥
⎦ and P=
⎡
⎢⎢
⎣
0111
0111
0111
0111
⎤
⎥⎥
⎦
The path matrixPshows there is no path from any node tov 1. HenceGis not strongly connected.
9.8. Consider the adjacency matrixAof the graphGin Fig. 9-19(a) obtained in Problem 9.7. Find the path
matrixPofGusing Warshall’s algorithm rather than the powers ofA.
Initially setP 0 =A. Then,P 1 ,P 2 ,P 3 ,P 4 are obtained recursively by setting
Pk[i, j]=Pk− 1 [i, j]∨(Pk− 1 [i, k]∧Pk− 1 [k, j])
wherePk[i, j] denotes theij-entry in the matrixPk.That is, by setting
Pk[i, j]=1ifPk− 1 [i, j]=1 or if both Pk− 1 [i, k]=1 and Pk− 1 [k, j]= 1
Then matricesP 1 ,P 2 ,P 3 ,P 4 follow:
P 1 =
⎡
⎢⎢
⎣
0111
0001
0101
0010
⎤
⎥⎥
⎦,P^2 =
⎡
⎢⎢
⎣
0111
0001
0101
0010
⎤
⎥⎥
⎦,P^3 =
⎡
⎢⎢
⎣
0111
0001
0101
0111
⎤
⎥⎥
⎦,P^4 =
⎡
⎢⎢
⎣
0111
0111
0111
0111
⎤
⎥⎥
⎦
Observe thatP 1 =P 2 =A. The changes inP 3 occur for the following reasons:
P 3 [ 4 , 2 ]=1 because P 2 [ 4 , 3 ]=1 andP 2 [ 3 , 2 ]= 1
P 3 [ 4 , 4 ]=1 because P 2 [ 4 , 3 ]=1 andP 2 [ 3 , 4 ]= 1
9.9. Draw a picture of the weighted graphGwhich is maintained in memory by the following vertex array DATA
and weight matrixW:
DATA:X, Y, S, T; W=
⎡
⎢
⎢
⎣
0030
5017
2004
0680
⎤
⎥
⎥
⎦
The picture appears in Fig. 9-24(a). The vertices are labeled by the entries in DATA.
Assumingv 1 =X,v 2 =Y,v 3 =S,v 4 =T, the order the vertices appear in the array DATA, we draw an edge
fromvitovjwith weightwijwhenwij=0.