Page 620 - Discrete Mathematics and Its Applications

9.4 Closures of Relations 599

R ={(1, 3), (1, 4), (2, 1), (3, 2)} on the set {1, 2, 3, 4}. This relation is not transitive because
it does not contain all pairs of the form (a, c) where (a, b) and (b, c) are in R. The pairs of
this form not in R are (1, 2), (2, 3), (2, 4), and (3, 1). Adding these pairs does not produce a
transitive relation, because the resulting relation contains (3, 1) and (1, 4) but does not contain
(3, 4). This shows that constructing the transitive closure of a relation is more complicated than
constructing either the reflexive or symmetric closure. The rest of this section develops algo-
rithms for constructing transitive closures. As will be shown later in this section, the transitive
closure of a relation can be found by adding new ordered pairs that must be present and then
repeating this process until no new ordered pairs are needed.

Paths in Directed Graphs

We will see that representing relations by directed graphs helps in the construction of transitive
closures. We now introduce some terminology that we will use for this purpose.
A path in a directed graph is obtained by traversing along edges (in the same direction as
indicated by the arrow on the edge).

DEFINITION 1 A path from a to b in the directed graph G is a sequence of edges (x 0 ,x 1 ), (x 1 ,x 2 ),
(x 2 ,x 3 ),...,(x n−1 ,x n ) in G, where n is a nonnegative integer, and x 0 = a and x n = b,
that is, a sequence of edges where the terminal vertex of an edge is the same as the initial
vertex in the next edge in the path. This path is denoted by x 0 ,x 1 ,x 2 ,...,x n−1 ,x n and has
length n. We view the empty set of edges as a path of length zero from a to a. A path of
length n ≥ 1 that begins and ends at the same vertex is called a circuit or cycle.

A path in a directed graph can pass through a vertex more than once. Moreover, an edge in
a directed graph can occur more than once in a path.

EXAMPLE 3 Which of the following are paths in the directed graph shown in Figure 1: a, b, e, d; a, e, c, d, b;
b, a, c, b, a, a, b; d, c; c, b, a; e, b, a, b, a, b, e? What are the lengths of those that are paths?
Which of the paths in this list are circuits?

Solution: Because each of (a, b), (b, e), and (e, d) is an edge, a, b, e, d is a path of length three.
Because (c, d) is not an edge, a, e, c, d, b is not a path. Also, b, a, c, b, a, a, b is a path of
length six because (b, a), (a, c), (c, b), (b, a), (a, a), and (a, b) are all edges. We see that d, c
is a path of length one, because (d, c) is an edge. Also c, b, a is a path of length two, because
(c, b) and (b, a) are edges. All of (e, b), (b, a), (a, b), (b, a), (a, b), and (b, e) are edges, so
e, b, a, b, a, b, e is a path of length six.
The two paths b, a, c, b, a, a, b and e, b, a, b, a, b, e are circuits because they begin and
end at the same vertex. The paths a, b, e, d; c, b, a; and d, c are not circuits. ▲

a b c

d e

FIGURE 1 A Directed Graph.