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

CHAP. 8] GRAPH THEORY 187

8.24. Draw the graphGcorresponding to each adjacency matrix:

(a) A=

⎡

⎢

⎢⎢

⎢

⎣

01010

10011

00011

11101

01110

⎤

⎥

⎥⎥

⎥

⎦

; (b) A=

⎡

⎢⎢

⎣

1300

3011

0122

0120

⎤

⎥⎥

⎦

(a) SinceAis a 5-square matrix,Ghas five vertices, say,v 1 ,v 2 ...,v 5. Draw an edge fromvitovjwhenaij=1. The

graph appears in Fig. 8-52(a).

(b) SinceAis a 4-square matrix,Ghas four vertices, say,v 1 ,...,v 4. Drawnedges fromvitovjwhenaij=n. Also,

drawnloops atviwhenai=n. The graph appears in Fig. 8-52(b).

Fig. 8-52

8.25. Find the weight matrixW=[wij]of the weighted graphGin Fig. 8-53(a)where the vertices are stored

in the array DATA as follows: DATA:A,B,C,X,Y.

Fig. 8-53

The vertices are numbered according to the way they are stored in the array DATA; sov 1 =A,v 2 =B,...,

v 5 =Y. Then setWij=w, wherewis the weight of the edge fromvitovj. This yields the matrixWin Fig. 8-53(b).

LINKEDREPRESENTATIONOFGRAPHS

8.26. A graphGwithverticesA,B,...,Fis stored in memory using a linked representation with a vertex file

and an edge file as in Fig. 8-54.

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

(b) Find the adjacency list adj(v)of each vertexvofG.

(a) Since START=4, the list begins with the vertexD. The NEXT-V tells us to go to 1(B), then 3(F ), then 5(A),

then 8(E), and then 7(C); that is,

D, B, F, A, E, C