CHAP. 9] DIRECTED GRAPHS 229
Fig. 9-29ROOTED TREES, ORDERED ROOTED TREES
9.24. LetTbe the rooted tree in Fig. 9-29(b).
(a) Identify the pathαfrom the rootRto each of the following vertices, and find the level number of the vertex:
(i)D; (ii)J; (iii)G.
(b) Find the leaves ofT.
(c) AssumingTis an ordered rooted tree, find the universal address of each leaf ofT.
9.25.The following addresses are in random order:
2. 1. 1 , 3. 1 , 2. 1 , 1 , 2. 2. 1. 2 , 0 , 3. 2 , 2. 2 , 1. 1 , 2 , 3. 1. 1 , 2. 2. 1 , 3 , 2. 2. 1. 1
(a) Place the addresses in lexicographic order.
(b) Draw the corresponding rooted tree.SEQUENTIAL REPRESENTATION OF GRAPHS
9.26. LetGbe the graph in Fig. 9-30(a).
(a) Find the adjacency matrixAand the path matrixPforG.
(b) For allk>0, findnkwherenkdenotes the number of paths of lengthkfromv 1 tov 4.
(c) IsGweakly, unilaterally, or strongly connected?Fig. 9-309.27. Repeat Problem 9.26 for the graphGin Fig. 9-30(b).
9.28. Let P be the path matrix for a graphG. DescribePwhenGis: (a) strongly connected; (b) unilaterally connected.
9.29. Let G be the graph in Fig. 9-31(a) where the vertices are maintained in memory by the array
DATA:X, Y, Z, S, T. (a) Find the adjacency matrixAand the path matrixPofG. (b) Find all cycles inG.
(c) IsGunilaterally connected? Strongly connected?
9.30. LetGbe the weighted graph in Fig. 9-31(b) where the vertices are maintained in memory by the array
DATA:X, Y, S, T.
(a) Find the weight matrixWofG.
(b) Find the matrixQof shortest paths using Warshall’s algorithm.