232 DIRECTED GRAPHS [CHAP. 9
9.43. Suppose a graphGis input by means of an integerM, representing the vertices 1, 2 ,...,M, and a list ofNordered
pairs of integers representing the edges ofG. Write a procedure for each of the following:
(a) Finds theM×Madjacency matrixAof the graphG.
(b) UsesAand Warshall’s algorithm to find the path matrixPofG.Test the above procedure using the following data:(i)M= 5 ;N= 8 ;( 3 , 4 ), ( 5 , 3 ), ( 2 , 4 ), ( 1 , 5 ), ( 3 , 2 ), ( 4 , 2 ), ( 3 , 1 ), ( 5 , 1 )
(ii)M= 6 ;N= 10 ;( 1 , 6 ), ( 2 , 1 ), ( 2 , 3 ), ( 3 , 5 ),( 4 , 5 ), ( 4 , 2 ), ( 2 , 6 ), ( 5 , 3 ), ( 4 , 3 ), ( 6 , 4 )9.44. Suppose a graphGis input by means of an integerM, representing the vertices 1, 2,...,M, and a list ofNordered
triples (ai,bi,wi)of integers such that (ai,bi)is an edge ofGandwiis its weight. Write a procedure for each of the
following:(a) Finds theM×Mweight matrixWof the graphG.
(b) UsesWand Warshall’s algorithm to find the matrixQof shortest paths between the vertices ofG.Test the above procedure using the following data:(i)M= 4 ;N= 7 ;( 1 , 2 , 5 ), ( 2 , 4 , 2 ), ( 3 , 2 , 3 ), ( 1 , 1 , 7 ), ( 4 , 1 , 4 ), ( 4 , 3 , 1 )
(ii)M= 5 ;N= 8 ;( 3 , 5 , 3 ), ( 4 , 1 , 2 ), ( 5 , 2 , 2 ), ( 1 , 5 , 5 ), ( 1 , 3 , 1 ),( 2 , 4 , 1 ), ( 3 , 4 , 4 ), ( 5 , 4 , 4 )9.45. Consider the graphGin Fig. 9-11. Show the sequence of waiting lists in STACK and the sequence of vertices processed
while doing a depth-first search (DFS) ofGbeginning at the vertex: (a)B; (b)E; (c)K.
9.46. Consider the graph in Fig. 9-11. As in Example 9.11, find the shortest path fromKtoFusing a breadth-first search
ofG. In particular, show the sequence of waiting lists in QUEUE during the search.Answers to Supplementary Problems
Notation:M=[R 1 ;R 2 ;...;Rn] denotes a matrix
wih rowsR 1 ,R 2 ,...,Rn.
9.18. (a) Indegrees: 1, 1, 4, 3, 1; outdegrees: 2, 3, 1, 2, 2.
(b) None.
(c) (v 1 ,v 2 ,v 4 ), (v 1 ,v 3 ,v 5 ,v 4 ), (v 1 ,v 2 ,v 3 ,v 5 ,v 4 )
(d) (v 3 ,v 5 ,v 4 ,v 3 )
(e) (v 1 ,v 3 ),(v 1 ,v 2 ,v 3 ),(v 1 ,v 2 ,v 4 ,v 3 ), (v 1 ,v 2 ,v 1 ,v 3 )
(v 1 ,v 3 ,v 5 ,v 7 )
(f) Unilaterally, but not strongly.
9.19. (a) Sources:v 1
(b) (v 1 ,v 6 ,v 7 ,v 4 ), (v 1 ,v 6 ,v 7 ,v 2 ,v 5 ,v 3 ,v 4 )
(c) (v 1 ,v 6 ,v 7 ,v 2 ,v 6 ,v 7 ,v 4 )
(d) (v 4 ,v 8 ,v 7 ,v 4 ), (v 4 ,v 8 ,v 7 ,v 2 ,v 5 ,v 3 ,v 4 )
9.20. (a) succ(1)=[6], succ(3)=[4, 7], succ(5)=[3],
succ(7)=[2, 4].
(b) (i) (1, 6), (5, 3); (ii) (2, 6), (6, 7), (7, 2), (3, 7).
9.21. (a)G=[A:D;B:C;C:E;D:B, D, E;E:A]
(b) Loop:(D, D)
(c)(D, E),(D,B,C,E)
(d)(A,D,E,A),(A,D,B,C,E,A)
(e) Unilaterally, and strongly.
(f) And (g)Hhas three edges:(C, E),(D, E),
(D, D). There are 8= 23 ways of choosing some
of the three edges; and each choice gives a subgraph.9.22. (a)(a, b),(a, c),(c, d),(c, e),(d, a),(d, b),(d, e)
(b) Sincebandeare sinks, there is no path frombtoe
or frometob,soGis neither unilaterally nor strongly
connected.Gis weakly connected since,cc,a,b,d,e
is a spanning semipath.
9.23. (a)G=[A:B, C:B:E;C:D;E:];(b)Sink:
E; (c)(A,B,E),(A,C,D,E); (d)(A,C,D,A);
(e)C, D, A, B, E); (f) No.
9.24. (a) (i) (R,A,D), 2; (ii)(R,B,F,J),3;
(iii)(R,C,G),2.
(b)H, E, I, J, G
(c)H: 1. 1 .1,E: 1 .2,I: 2. 1 .1,J: 2. 1 .2,G: 3. 1
9.25. (a) 0, 1, 1.1, 2, 2.1, 2.1.1, 2.2, 2.2.1, 2.2.1.1, 2.2.1.2,
3, 3.1, 3.1.1, 3.2. (b) Fig. 9-35(a).
9.26. (a)A=[ 0 , 1 , 1 , 0 ; 0 , 0 , 1 , 1 ; 0 , 0 , 0 , 1 ; 0 , 0 , 0 , 0 ];
P=[ 0 , 1 , 1 , 1 ; 0 , 0 , 1 , 1 ; 0 , 0 , 0 , 1 ; 0 , 0 , 0 , 0 ];
(b) 0,2, 1, 0, 0,...; (c) Weakly and unilaterally.
9.27. (a)A=[ 0 , 1 , 1 , 0 ; 0 , 0 , 0 , 0 ; 0 , 1 , 1 , 1 ; 0 , 2 , 0 , 0 ];
P=[ 0 , 1 , 1 , 1 ; 0 , 0 , 0 , 0 ; 0 , 1 , 1 , 1 ; 0 , 1 , 0 , 0 ];
(b) 0,1, 1, 1,...; (c) Weakly and unilaterally.
9.28. LetP=[pij]. Fori = j: (a)pij=0; (b) either
pij=0orpji=0.