CHAP. 9] DIRECTED GRAPHS 231
Fig. 9-33
9.36. Using the data in Fig. 9-33, write a procedure with input CITYXand CITYYwhich finds the flight number of a direct
flight from cityXto cityY, if it exists. Test the procedure using:
(a) X=Atlanta,Y=Philadelphia; (c)X=Houston,Y=Chicago;
(b) X=Philadelphia,Y=Atlanta; (d)X=Washington,Y=Chicago.
9.37. Using the data in Fig. 9-33, write a procedure with input CITYXand CITYYwhich finds the most direct route
(minimum number of stops) from cityXto cityY, if it exists. Test the procedure using the input in Problem 9.36.
MISCELLANEOUS PROBLEMS
9.38. Use the pruning algorithm to find the shortest path fromstotin Fig. 9-34.
Fig. 9-34
9.39. Find a topological sortTof each of the following graphs:
(a)G=[A:Z; B:T; C:B; D:; X:D; Y:X; Z:B, X; S:C, Z; T:]
(b)G=[A:X, Z; B:A; C:S, T; D:Y; X:S, T; Y:B; Z:; S:Y; T:]
(c)G=[A:C, S; B:T,Z; C:; D:Z; X:A; Y:A; Z:X, Y; S:; T:Y]
9.40. Draw a labeled graphGthat represents the following situation. Three sisters, Barbara, Rose, and Susan, each regularly
telephone their mother Gertrude, though Gertrude calls only Rose. Susan will not call Rose, though Rose continues to
call Susan. Barbara and Susan will call each other, and Barbara and Rose will call each other.
9.41. LetRbe the relation (directed graph) onV ={ 2 , 3 , 4 , 9 , 15 }defined by βxis less than and relatively prime toy.β
(a) Draw the diagram of the graphR. (b) IsRweakly connected? Unilaterally connected? Strongly connected?
9.42.A directed graphGiscompleteif, for each pair of distinct verticesuandv, either(u, v)is an arc or(v, u)is an
arc. Show that a finite complete directed graphGhas a path which includes all vertices. (This obviously holds for
non-directed complete graphs.) ThusGis unilaterally connected.