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

CHAP. 9] DIRECTED GRAPHS 225

Fig. 9-24

LINKED REPRESENTATION OF GRAPHS

9.10. LetGbe the graph presented by the following table:

G=[X:Y, Z, W; Y:X, Y, W; Z:Z, W; W:Z]

(a) Find the number of vertices and edges inG.

(b) Draw the graph ofG.

(c) Are there any sources or sinks?

(a) The table tells us that there are four vertices,X, Y, Z, W. The outdegrees of the vertices are 3, 3, 2, 1, respectively.

Thus there are 3+ 3 + 2 + 1 =9 edges.

(b) Using the adjacency lists, draw the graph in Fig. 9-24(b).

(c) No vertex has zero outdegree, so there are no sinks. Also, no vertex has zero indegree, that is, each vertex is a

successor; hence there are no sources.

9.11. 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-25(a).

Fig. 9-25

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

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

(c) Draw the graph ofG.