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

188 GRAPH THEORY [CHAP. 8

(b) Here adj(D)=[ 5 (A), 1 (B), 8 (E)]. Specifically, PTR[ 4 (D)]=7 and ADJ[ 7 ]= 5 (A)tells us that adj(D)begins

withA. Then NEXT[ 7 ]=3 and ADJ[ 3 ]= 1 (B)tells us thatBis the next vertex in adj(D). Then NEXT[ 3 ]= 10

and ADJ[ 10 ]= 8 (E)tells us thatEin the next vertex in adj(D). However, NEXT[ 10 ]=0 tells us that there are

no more neighbors ofD. Similarly.

adj(B)=[A, D], adj(F )=[E], adj(A)=[B, D], adj(E)=[C, D, F], adj(C)=[E]

In other words, the following is the adjacency structure ofG:

G=[A:B,D; B:A, D; C:E; D:A, B, E; E:C, D, F; F:E]

Fig. 8-54

8.27. Draw the diagram of the graphGwhose linked representation appears in Fig. 8-54.

Use the vertex list obtained in Problem 8.26(a) and the adjacency lists obtained in Problem 8.26(b) to draw the graph

Gin Fig. 8-55.

Fig. 8-55

8.28. Exhibit the adjacency structure (AS) of the graphGin: (a) Fig. 8-56(a),(b) Fig. 8-56(b).

The adjacency structure of a graphGconsists of the adjacency lists of the vertices where we use a colon“:” to separate

a vertex from its adjacency list, and a semicolon “;” to separate the different lists. Thus:

(a) G=[A:B, C, D; B:A, C, E; C:A, B, D, E; D:A, C; E:B, C]

(b) G=[A:B, D; B:A, C, E; C:B, E, F; D:A, E; E:B, C, D, F; F:C, E]

GRAPH ALGORITHMS

8.29. Consider the graphGin Fig. 8-56(a)(where the vertices are ordered alphabetically).

(a) Find the adjacency structure ofG.

(b) Find the order in which the vertices ofGare processed using a DFS (depth-first search) algorithm

beginning at vertexA.

(a) List the neighbors of each vertex as follows:

G=[A:B, C, D; B:A, J; C:A; D:A, K; J:B, K, M; K:D, J, L; L:K, M; M:J, L]