Page 691 - Discrete Mathematics and Its Applications

670 10 / Graphs

Note that an adjacency matrix of a graph is based on the ordering chosen for the vertices.
Hence, there may be as many as n! different adjacency matrices for a graph with n vertices,
because there are n! different orderings of n vertices.
The adjacency matrix of a simple graph is symmetric, that is, a ij = a ji , because both of
these entries are 1 when v i and v j are adjacent, and both are 0 otherwise. Furthermore, because
a simple graph has no loops, each entry a ii ,i = 1, 2, 3,...,n,is0.
Adjacency matrices can also be used to represent undirected graphs with loops and with
multiple edges. A loop at the vertex v i is represented bya1atthe (i, i)th position of the
adjacency matrix. When multiple edges connecting the same pair of vertices v i and v j ,or
multiple loops at the same vertex, are present, the adjacency matrix is no longer a zero–one
matrix, because the (i, j)th entry of this matrix equals the number of edges that are associated
to {v i , v j }. All undirected graphs, including multigraphs and pseudographs, have symmetric
adjacency matrices.

EXAMPLE 5 Use an adjacency matrix to represent the pseudograph shown in Figure 5.

a b
Solution: The adjacency matrix using the ordering of vertices a, b, c, d is
⎡ ⎤
0 3 0 2
⎢ 3 0 1 1 ⎥ .
⎥
⎢
0 1 1 2
⎣ ⎦
d c 2 1 2 0
▲
FIGURE 5
We used zero–one matrices in Chapter 9 to represent directed graphs. The matrix for a
A Pseudograph.
directed graph G = (V, E) hasa1inits (i, j)th position if there is an edge from v i to v j ,
where v 1 , v 2 ,..., v n is an arbitrary listing of the vertices of the directed graph. In other words,
if A =[a ij ] is the adjacency matrix for the directed graph with respect to this listing of the
vertices, then

1 if (v i , v j ) is an edge of G,
a ij =
0 otherwise.

The adjacency matrix for a directed graph does not have to be symmetric, because there may
not be an edge from v j to v i when there is an edge from v i to v j .
Adjacency matrices can also be used to represent directed multigraphs.Again, such matrices
are not zero–one matrices when there are multiple edges in the same direction connecting two
vertices. In the adjacency matrix for a directed multigraph, a ij equals the number of edges that
are associated to (v i , v j ).

TRADE-OFFS BETWEEN ADJACENCY LISTS AND ADJACENCY MATRICES When
a simple graph contains relatively few edges, that is, when it is sparse, it is usually preferable
to use adjacency lists rather than an adjacency matrix to represent the graph. For example, if
each vertex has degree not exceeding c, where c is a constant much smaller than n, then each
adjacency list contains c or fewer vertices. Hence, there are no more than cn items in all these
2
adjacency lists. On the other hand, the adjacency matrix for the graph has n entries. Note,
however, that the adjacency matrix of a sparse graph is a sparse matrix, that is, a matrix with
few nonzero entries, and there are special techniques for representing, and computing with,
sparse matrices.
Now suppose that a simple graph is dense, that is, suppose that it contains many edges, such
as a graph that contains more than half of all possible edges. In this case, using an adjacency
matrix to represent the graph is usually preferable over using adjacency lists. To see why, we
compare the complexity of determining whether the possible edge {v i , v j } is present. Using an
adjacency matrix, we can determine whether this edge is present by examining the (i, j)th entry