CHAP. 8] GRAPH THEORY 195
8.68. Draw the multigraphGcorresponding to each of the following adjacency matrices:(a)A=⎡
⎢
⎢
⎣0201
2111
0101
1110⎤
⎥
⎥
⎦; (b)A=⎡
⎢
⎢
⎣1112
1000
1002
2022⎤
⎥
⎥
⎦8.69. Suppose a graphGis bipartite. Show that one can order the vertices ofGso that its adjacency matrixAhas the form:
A=[
0 B
C 0]LINKED REPRESENTATION OF GRAPHS
8.70. Suppose a graphGis stored in memory as in Fig. 8-67.Fig. 8-67(a) List the vertices in the order in which they appear in memory.
(b) Find the adjacency structure ofG, that is, find the adjacency list adj(v)of each vertexvofG.8.71. Exhibit the adjacency structure (AS) for each graphGin Fig. 8-59.
8.72. Figure 8-68(a)shows a graphGrepresenting six citiesA,B,...,Fconnected by seven highways numbered
22, 33,..., 88. Show howGmay be maintained in memory using a linked representation with sorted arrays for
the cities and for the numbered highways. (Note that VERTEX is a sorted array and so the field NEXT-V is not
needed.)Fig. 8-68