206 DIRECTED GRAPHS [CHAP. 9
Fig. 9-3identical to the order obtained by moving down the leftmost branch of the tree, then the next branch to the right,
then the second branch to the right, and so on.
9.5Sequential Representation of Directed Graphs
There are two main ways of maintaining a directed graphGin the memory of a computer. One way, called
thesequential representationofG, is by means of its adjacency matrixA. The other way, called thelinked
representationofG, is by means of linked lists of neighbors. This section covers the first representation. The
linked representation will be covered in Section 9.7.
Suppose a graphGhasmvertices (nodes) andnedges. We sayGisdenseifm=O(n^2 )andsparseif
m=O(n) or even ifm=O(nlogn). The matrix representation ofGis usually used whenGis dense, and
linked lists are usually used whenGis sparse. Regardless of the way one maintains a graphGin memory, the
graphGis normally input into the computer by its formal definition, that is, as a collection of vertices and a
collection of edges (pairs of vertices).
Remark: In order to avoid special cases of our results, we assume, unless otherwise stated, thatm>1 wherem
is the number of vertices in our graphG. Therefore,Gis not connected ifGhas no edges.
Digraphs and Relations, Adjacency Matrix
LetG(V, E)be asimpledirected graph, that is, a graph without parallel edges. ThenEis simply a subset
ofV×V, and henceEis a relation onV. Conversely, ifRis a relation on a setV, thenG(V, R)is a simple
directed graph. Thus the concepts of relations on a set and simple directed graphs are one and the same. In fact,
in Chapter 2, we already introduced the directed graph corresponding to a relation on a set.
SupposeGis a simple directed graph withmvertices, and suppose the vertices ofGhave been ordered and
are calledv 1 ,v 2 ,...,vm. Then theadjacency matrixA=[aij]ofGis them×mmatrix defined as follows:
aij={
1 if there is an edge(vi,vj)
0 otherwiseSuch a matrixA, which contains entries of only 0 or 1, is called abit matrixor aBoolean matrix. (Although the
adjacency matrix of an undirected graph is symmetric, this is not true here for a directed graph.)
The adjacency matrixAof the graphGdoes depend on the ordering of the vertices ofG. However, the
matrices resulting from two different orderings are closely related in that one can be obtained from the other by
simply interchanging rows and columns. Unless otherwise stated, we assume that the vertices of our matrix have
a fixed ordering.
Remark: The adjacency matrixA=[aij]may be extended to directed graphs with parallel edges by setting:
aij=the number of edges beginning atviand ending atvj