 Representing graphsOne way to represent a graph without multiple edges is to list all the edges of this graph. Another way to represent a graph with no multiple edges is to use adjacency lists, which specify the vertices that are adjacent to each vertex of the graph.
Example. Use adjacency lists to describe the simple graph given in Figure below.
Solution:
An edge list for a simple graph
 Vertex
 Adjacent vertices
 a
b
c
d
e
 b, c, e
a
a, d, e
c, e
a, c, d
 Example. Represent the directed graph by listing all the vertices that are the terminal vertices of edges starting at each vertex of the graph.
Solution:
An edge list for a directed graph
 Initial vertex
 Terminal vertex
 a
b
c
d
e
 b, c, d, e
b, d
a, c, e
b, c, d

Adjacency matrices
Suppose that is a simple graph where . Suppose that the vertices of G are listed arbitrarily as . The adjacency matrix A (or A_{G}) of G, with respect to this listing of the vertices, is the zeroone 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 , then .
Example. Use an adjacency matrix to represent the graph shown in Figure below.
Solution: We order the vertices as a, b, c, d. The matrix representing this graph is .
Example. Draw a graph with the adjacency matrix with respect to the ordering of vertices a, b, c, d.
Solution:
Adjacency matrices can also be used to represent undirected graphs with loops and with multiple edges. A loop at the vertex a_{i} is represented by a 1 at the (i, i)^{th} position of the adjacency matrix. When multiple edges are present, the adjacency matrix is no longer a zeroone matrix, since the (i, j)^{th} entry of this matrix equals the number of edges that are associated to .
Example. Use an adjacency matrix to represent the pseudograph shown in Figure below.
Solution: The adjacency matrix using the ordering of vertices a, b, c, d is .
Date: 20150102; view: 687
