Page 690 - Discrete Mathematics and Its Applications

10.3 Representing Graphs and Graph Isomorphism 669

b TABLE 2 An Adjacency List for a
Directed Graph.
a c
Initial Vertex Terminal Vertices

a b, c, d, e
b b, d
c a, c, e
e d d
e b, c, d
FIGURE 2 A Directed Graph.

EXAMPLE 2 Represent the directed graph shown in Figure 2 by listing all the vertices that are the terminal
vertices of edges starting at each vertex of the graph.
a b
Solution: Table 2 represents the directed graph shown in Figure 2. ▲

Adjacency Matrices

c d Carrying out graph algorithms using the representation of graphs by lists of edges, or by adja-
cency lists, can be cumbersome if there are many edges in the graph. To simplify computation,
FIGURE 3 graphs can be represented using matrices. Two types of matrices commonly used to represent
Simple Graph. graphs will be presented here. One is based on the adjacency of vertices, and the other is based
on incidence of vertices and edges.
Suppose that G = (V, E) is a simple graph where |V |= n. Suppose that the vertices of
G are listed arbitrarily as v 1 , v 2 ,..., v n . The adjacency matrix A (or A G )of G, with respect
to this listing of the vertices, is the n x n zero–one matrix with 1 as its (i, j)th entry when v i
and v j are adjacent, and 0 as its (i, j)th entry when they are not adjacent. In other words, if its
adjacency matrix is A =[a ij ], then

1 if {v i , v j } is an edge of G,
a ij =
0 otherwise.
EXAMPLE 3 Use an adjacency matrix to represent the graph shown in Figure 3.

Solution: We order the vertices as a, b, c, d. The matrix representing this graph is
⎡ ⎤
0 1 1 1
⎢ 1 0 1 0 ⎥ .
⎢
⎥
1 1 0 0
⎣ ⎦
1 0 0 0
▲
EXAMPLE 4 Draw a graph with the adjacency matrix
a b
⎡ ⎤
0 1 1 0
⎢ 1 0 0 1 ⎥
⎥
⎢
⎣ 1 0 0 1 ⎦
0 1 1 0
d c
with respect to the ordering of vertices a, b, c, d.
FIGURE 4
A Graph with the
Given Adjacency
Matrix. Solution: A graph with this adjacency matrix is shown in Figure 4. ▲