Schaum's Outline of Discrete Mathematics, Third Edition (Schaum's Outlines)

230 DIRECTED GRAPHS [CHAP. 9

Fig. 9-31

LINKED REPRESENTATION OF GRAPHS

9.31.A weighted graphGwith six vertices,A, B, ..., F, is stored in memory using a linked representation with a vertex

file and an edge file as in Fig. 9-32.

(a) List the vertices in the order they appear in memory.

(b) Find the successor list succ(v) of each vertexvinG.

(c) Draw a picture ofG.

Fig. 9-32

9.32. LetGbe the graph presented by the table:G=[A:B, C; B:C, D; C:C; D:B; E:
].

(a) Find the number of vertices and edges inG. (c) Are there any sources or sinks?

(b) Draw a picture ofG. (d) IsGweakly, unilaterally, or strongly connected?

9.33. Repeat Problem 9.32 for the table:G=[A:D; B:C; C:E; D:B, D, E; E:A].

9.34. Repeat Problem 9.32 for the table:G=[A:B, C, D, K; B:J; C:
;D:
; J:B, D, L; K:D, L; L:D].

9.35. Suppose Friendly Airways has eight daily flights serving the seven cities: Atlanta, Boston, Chicago, Denver, Houston,

Philadelphia, Washington. Suppose the data on the flights are stored in memory as in Fig. 9-33; that is, using a linked

representation where the cities and flights appear in linear sorted arrays. Draw a labeled directed graphGdescribing

the data.