Chapter 6: Directed graphs
6.1 Definition and examples of digraphs
Introduction
In this chapter we discuss digraphs and their properties. Our treatment of the subject is similar to
that of Chapters 5 for graphs, except that we need to take account of the directions of the arcs.
Definition: A directed graph (digraph) consists of a set of elements called vertices and a set of
elements called arcs. Each arc joins two vertices in a specified direction.
Example 1: The digraph shown below has four vertices {𝑢, 𝑣, 𝑤, 𝑥} and six arcs {1,2,3,4,5,6}.
Arc 1 joins 𝑥 to 𝑢, arc 2 joins 𝑢 to 𝑤, arcs 3 and 4 join 𝑤 to 𝑣, arc 5 joins 𝑥 to 𝑤, and arc 6 joins
the vertex 𝑥 to itself.
We often denote an arc by specifying its two vertices in order; for example, arc 1 is denoted by
𝑥𝑢, arcs 3 and 4 are denoted by 𝑤𝑣, and arc 6 is denoted by 𝑥𝑥. Note that 𝑥𝑢 is not the same as
𝑢𝑥.
The above digraph contains more than one arc joining 𝑤 to 𝑣, and an arc joining the vertex 𝑥 to
itself.
Definition: In a digraph, two or more arcs joining the same pair of vertices in the same
direction are multiple arcs. An arc joining a vertex to itself is a loop. A digraph with no
multiple arcs or loops is a simple digraph.
Example 2: Digraph (a) below has multiple arcs and digraph (b) has a loop, so neither is a
simple digraph. Digraph (c) has no multiple arcs or loops, and is therefore a simple digraph.
1
Adjacency and Incidence
The digraph analogues of adjacency and incidence are similar to the corresponding definitions
for graphs, except that we take account of the directions of the arcs.
Definition: The vertices 𝑣 and 𝑤 of a digraph are adjacent vertices if they are joined (in either
direction) by an arc 𝑒. An arc 𝑒 that joins 𝑣 to 𝑤 is incident from v and incident to 𝑤; 𝑣 is
incident to 𝒆, and 𝑤 is incident from 𝑒.
Example 3: In the digraph below, the vertices 𝑢 and 𝑥 are adjacent, vertex 𝑤 is incident from
arcs 2 and 5 and incident to arcs 3 and 4, and arc 6 is incident to (and from) the vertex 𝑥.
Isomorphism
It follows from the definition that a digraph is completely determined when we know its vertices
and arcs, and that two digraphs are the same if they have the same vertices and arcs. Once we
know the vertices and arcs, we can draw the digraph and, in principle, any picture we draw is as
good as any other; the actual way in which the vertices and arcs are drawn is irrelevant -
although some pictures are easier to use than others!
We extend the concept of isomorphism to digraphs, as follows.
Definition: Two digraphs C and D are isomorphic if D can be obtained by relabeling the
vertices of C - that is, if there is a one-one correspondence between the vertices of C and those of
2
D, such that the arcs joining each pair of vertices in C agree in both number and direction with
the arcs joining the corresponding pair of vertices in D.
Example 4: The digraphs C and D represented by the diagrams
are not the same, but they are isomorphic, since we can relabel the vertices in the digraph C to
get the digraph D, using the following one-one correspondence:
Note that arcs in C correspond to arcs in D - for example: the two arcs from 𝑢 to 𝑣 in C
correspond to the two arcs from 2 to 3 in D; the arcs 𝑤𝑥and 𝑥𝑤 in C correspond to the arcs 41
and 14 in D; the loop 𝑤𝑤 in C corresponds to the loop 44 in D.
Definition: A sub digraph of a digraph D is a digraph all of whose vertices are vertices of D
and all of whose arcs are arcs of D.
Remark: Note that D is a sub digraph of itself.
Example 5: The following digraphs are all sub digraphs of the digraph D on the left, with
vertices {𝑢, 𝑣, 𝑤, 𝑥} and arcs {1, 2, 3, 4, 5, 6}.
3
The idea of a sub digraph can be extended to unlabelled digraphs.
Example 6: The following digraphs are all sub digraphs of the unlabelled digraph C on the left:
It is also convenient to introduce the idea of the underlying graph of a digraph.
Definition: The underlying graph of a digraph D is the graph obtained by replacing each arc
of D by the corresponding undirected edge.
To obtain the underlying graph, we simply remove the arrows from the arcs.
Example 7:
4
We now give analogues of the degree of a vertex in a graph.
Definition: In a digraph, the out-degree of a vertex 𝑣 is the number of arcs incident from 𝑣, and
is denoted by outdeg v; the in-degree of 𝑣 is the number of arcs incident to 𝑣, and is denoted by
indeg 𝑣.
Remark: Each loop contributes 1 to both the in-degree and the out-degree of the corresponding
vertex.
Example 8: The digraph below has the following out-degrees and in-degrees:
Outdeg 𝑢 = 1 outdeg 𝑣 = 3 outdeg 𝑤 = 2
Indeg 𝑢 = 0 indeg 𝑣 = 1 indeg 𝑤 = 1
Outdeg 𝑥 = 0 outdeg 𝑦 = 2 outdeg 𝑧 = 2
Indeg 𝑥 = 0 indeg 𝑦 = 6 indeg 𝑧 = 2
There are also analogues of the degree sequence of a graph, corresponding to the out-degree and
in-degree of a vertex.
Definition: The out-degree sequence of a digraph D is the sequence obtained by listing the
out-degrees of D in increasing order, with repeats as necessary. The in-degree sequence of D is
defined analogously.
Example 9: The above digraph has out-degree sequence (0, 1,2,2,2,3) and in-degree sequence
(0, 0, 1, 1, 2, 6).
5
Handshaking Dilemma
Theorem (Handshaking Dilemma): In any digraph, the sum of all the out-degrees and the sum
of all the in-degrees are both equal to the number of arcs.
Proof: In any digraph, each arc has two ends, so it contributes exactly 1 to the sum of the out-
degrees and exactly 1 to the sum of the in-degrees. The result follows immediately.
6.2 Matrix representation of digraphs
6.2.1 Adjacency Matrices
Consider the following example 1:
On the left we have a graph with four labelled vertices, and on the right we have a matrix with
four rows and four columns - that is, a 4 𝑥 4 matrix. The numbers appearing in the matrix refer to
the number of edges joining the corresponding vertices in the graph.
For example,
Vertices 1 and 2 are joined by 1 edge, so 1 appears in row 1 column 2, and in row 2 colum 1;
Vertices 2 and 4 are joined by 2 edges, so 2 appears in row 2 column 4, and in row 4 column
2;
Vertices 1 and 3 are joined by 0 edges, so 0 appears in row 1 column 3, and in row 3 column
1;
6
Vertex 2 is joined to itself by 1 edge, so 1 appears in row 2 column 2.
Definition: Let G be a graph with n vertices labelled 1,2,3, . . . , 𝑛. The adjacency matrix 𝐴( 𝐺)
of 𝐺 is the 𝑛 𝑥 𝑛 matrix in which the entry in row 𝑖 and column 𝑗 is the number of edges joining
the vertices 𝑖 and 𝑗.
The adjacency matrix of a graph is symmetrical about the main diagonal (top-left to bottom-
right). Also, for a graph without loops, each entry on the main diagonal is 0, and the sum of the
entries in any row or column is the degree of the vertex corresponding to that row or column.
Example 2: For the graph
The adjacency matrix is and The incidence matrix is
The representation of a graph by an adjacency matrix has a digraph analogue that is frequently
used when storing large digraphs in a computer. When defining the adjacency matrix of a
digraph, we have to take into account the directions of the arcs.
7
Example 3:
On the left we have a digraph with four labelled vertices, and on the right we have a matrix with
four rows and four columns. The numbers appearing in the matrix refer to the number of arcs
joining the corresponding vertices in the digraph.
For example,
Vertices 1 and 2 are joined (in that order) by 1 arc, so 1 appears in row 1 column 2;
Vertices 2 and 4 are joined (in that order) by 2 arcs, so 2 appears in row 2 column 4;
Vertices 4 and 1 are joined (in that order) by 0 arcs, so 0 appears in row 4 column 1;
Vertex 2 is joined to itself by 1 arc, so 1 appears in row 2 column 2.
Walks in Graphs and Digraphs
We can establish the existence of walks in a graph or digraph by using the adjacency matrix. In
the following, we restrict our attention to digraphs: similar results can be derived for graphs.
Consider the following digraph and table:
8
Example 4:
The table shows the number of walks of length 1 between each pair of vertices.
For example,
The number of walks of length 1 from 𝑎 to 𝑐 is 0, so 0 appears in row 1 column 3;
The number of walks of length 1 from 𝑏 to 𝑎 is 1, so 1 appears in row 2 column 1;
The number of walks of length 1 from 𝑑 to 𝑏 is 2, so 2 appears in row 4 column 2.
Now a walk of length 1 is an arc, so the table above is the adjacency matrix A of the digraph:
Next, we consider walks of lengths 2 and 3. For example, there are two different walks of length
2 from 𝑎 to 𝑏, because there is one arc from 𝑎 to 𝑑 and two arcs from 𝑑 to 𝑏. Similarly, there are
two different walks of length 3 from 𝑑 to 𝑑, since there are two arcs from 𝑑 to 𝑏, and one walk of
length 2 from 𝑏 to 𝑑, namely, 𝑏𝑎𝑑.
Counting walks
Let 𝐴 = (𝑎𝑖𝑗 ) be the adjacency matrix of a graph G with vertex set {𝑣1 , 𝑣2 , 𝑣3 , … 𝑣𝑛 }. The (𝑖, 𝑗)𝑡ℎ
element of 𝐴2 is ∑𝑛𝑘=1 𝑎𝑖𝑘 𝑎𝑘𝑗 and this is the number of walks of length 2 from 𝑣𝑖 to 𝑣𝑗 .
9
Example 5: If G is
Hence, for example, the number of walks of length 2 from 𝑣2 to 𝑣3 is 2, and the number of walks
of length 2 from 𝑣1 to 𝑣2 is 3.
Generally, for any positive integer 𝑟, the number of walks of length 𝑟 from 𝑣𝑖 to 𝑣𝑗 is given by
the (𝑖, 𝑗)𝑡ℎ element of 𝐴𝑟 .
6.1.2 Incidence Matrices
For convenience, in this section we restrict our attention to graphs all digraphs without loops.
Whereas the adjacency matrix of a graph or digraph involves the adjacency of vertices, the
incidence matrix involves the incidence of vertices and edges or arcs. To see what is involved,
consider the following example:
10
On the left we have a graph with four labelled vertices and six labelled edges, and on the righ t
we have a matrix with four rows and six columns. Each of the numbers appearing in the matrix is
1 or 0, depending on whether the corresponding vertex and edge are incident with each other. For
example,
Vertex ① is incident with edge 4, so 1 appears in row 1 column 4;
Vertex ②is not incident with edge 4, so 0 appears in row 2 column 4.
Definition: Let G be a graph without loops, with 𝑛 vertices labelled ①, ②, . . ., and 𝑚 edges
labelled 1,2,3, . . . , 𝑚. The incidence matrix 𝐈(𝐆) of G is the 𝑛 𝑥 𝑚 matrix in which the entry in
row 𝑖 and column 𝑗 is
In the incidence matrix of a graph without loops, each column contains exactly two 1s, as each
edge is incident with just two vertices; the sum of the numbers in a row is the degree of the
vertex corresponding to that row.
Whereas the adjacency matrix of a digraph involves the adjacency of vertices, the incidence
matrix of a digraph involves the incidence of vertices and arcs. Since an arc can be incident
from, incident to, or not incident with a vertex, we have to take account of this when defining the
matrix.
Example 6:
11
On the left we have a digraph with four labelled vertices and six labelled arcs, and on the right
we have a matrix with four rows and six columns. Each of the numbers appearing in the matrix is
1, −1 or 0, depending on whether the corresponding arc is incident from, incident to, or not
incident with, the corresponding vertex.
For example,
Arc 4 is incident from vertex ①, so 1 appears in row 1 column 4;
Arc 5 is incident to vertex ④, so -1 appears in row 4 column 5;
Arc 4 is not incident with vertex ②, so 0 appears in row 2 column 4.
Definition: Let D be a digraph without loops, with n vertices labelled 1, 2, … , 𝑛 and 𝑚 arcs
labelled 1, 2,3, … , 𝑚. The incidence matrix I(D) of D is the 𝑛 𝑥 𝑚 matrix in which the entry in
row 𝑖 and column 𝑗 is
In the incidence matrix of a digraph without loops, each column has exactly one 1 and one −1,
since each arc is incident from one vertex and incident to one vertex; the number of 1s in any
row is the out-degree of the vertex corresponding to that row, and the number of −1s in any row
is the in-degree of the vertex corresponding to that row.
6.3 Paths and connectivity
Just as you may be able to get from one vertex of a graph to another by tracing the edges of a
walk, trail or path, so you may be able to get from one vertex of a digraph to another by tracing
the arcs of a 'directed' walk, trail or path. This means that you have to follow the directions of the
arcs as you go, just as if you were driving around a one-way street system in a town.
Definition: A walk of length 𝑘 in a digraph is a succession of 𝑘 arcs of the form
𝑢𝑣, 𝑣𝑤, 𝑤𝑥, . . . , 𝑦𝑧. This walk is denoted by 𝑢𝑣𝑤𝑥 . . . 𝑦𝑧, and is referred to as a walk from 𝑢 to 𝑧.
A trail is a walk in which all the arcs, but not necessarily all the vertices, are different. A path is
a walk in which all the arcs and all the vertices are different.
12
Example 1: In the following diagram, the walk 𝑣𝑤𝑥𝑦𝑣𝑤𝑦𝑧𝑧𝑢 is a walk of length 9 from 𝑣 to 𝑢,
which includes the arc 𝑣𝑤 twice and the vertices 𝑣, 𝑤, 𝑦 and 𝑧 twice. The walk 𝑢𝑣𝑤𝑦𝑣𝑧 is a trail
which is not a path, since the vertex 𝑣 occurs twice, whereas the walk 𝑣𝑤𝑥𝑦𝑧 has no repeated
vertices and is therefore a path.
The terms closed walk, closed trail and cycle also apply to digraphs.
Definition: A closed walk in a digraph is a succession of arcs of the form
𝑢𝑣, 𝑣𝑤, 𝑤𝑥, . . . , 𝑦𝑧, 𝑧𝑢. A closed trail is a closed walk in which all the arcs are different. A cycle
is a closed trail in which all the intermediate vertices are different.
In the digraph above, the closed walk 𝑢𝑣𝑤𝑦𝑣𝑧𝑢 is a closed trail which is not a cycle (since the
vertex 𝑣 occurs twice), whereas the closed trails 𝑧𝑧, 𝑤𝑥𝑤, 𝑣𝑤𝑥𝑦𝑣 and 𝑢𝑣𝑤𝑥𝑦𝑧𝑢 are all cycles. In
describing closed walks, we can allow any vertex to be the starting vertex. For example, the
triangle 𝑣𝑤𝑦𝑣 can also be written as 𝑤𝑦𝑣𝑤 or 𝑦𝑣𝑤𝑦.
As with graphs, we can use the concept of a path tell us whether or not a digraph is connected.
Recall that a graph is connected if it is 'in one piece', and this means that there is a path between
each pair of vertices. For digraphs these two ideas are not the same, and this leads to two
different definitions of the word connected for digraphs.
Definition: A digraph is connected if its underlying graph is a connected graph, and is
disconnected otherwise. A digraph is strongly connected if there is a path between each pair of
vertices.
13
Example 2: These three types of digraph are illustrated below:
Digraph (a) is disconnected, since its underlying graph is a disconnected graph. Digraph (b) is
connected but is not strongly connected since, for example, there is no path from 𝑧 to 𝑦. Digraph
(c) is strongly connected, since there are paths joining all pairs of vertices.
Alternatively, you can think of driving around a one-way street system in a town. If the town is
strongly connected, then you can drive from any part of the town to any other, following the
directions of the one-way streets as you go; if the town is merely connected, then you can still
drive from any part of the town to any other, but you may have to ignore the directions of the
one-way streets!
Eulerian and Hamiltonian Digraphs
In Chapter 5, we discussed the problem of finding a route that includes every edge or every
vertex of a graph exactly once, and it is natural to consider the corresponding problem for
digraphs. This leads to the following definitions.
14
Definition: A connected digraph is Eulerian if it contains a closed trail that includes every arc;
such a trail is an Eulerian trail. A connected digraph is Hamiltonian if it contains a cycle that
includes every vertex; such a cycle is a Hamiltonian cycle.
Example 3: Consider the following four digraphs:
Digraph (𝑎) is Eulerian - an Eulerian trail is 𝑎𝑏𝑐𝑑𝑒𝑓𝑔𝑐𝑒𝑔𝑓𝑎 and Hamiltonian - a
Hamiltonian cycle is 𝑎𝑏𝑐𝑑𝑒𝑔𝑓𝑎;
Digraph (𝑏) is Eulerian - an Eulerian trail is 𝑏𝑐𝑔𝑓𝑒𝑔𝑏 it is not Han1iltonian;
Digraph (𝑐) is Hamiltonian - a Hamiltonian cycle is 𝑏𝑐𝑑𝑒𝑔𝑓𝑏 it is not Eulerian;
Digraph (𝑑) is neither Eulerian nor Hamiltonian.
15