Page 622 - Discrete Mathematics and Its Applications

9.4 Closures of Relations 601

EXAMPLE 5 Let R be the relation on the set of all subway stops in NewYork City that contains (a, b) if it is
n
possible to travel from stop a to stop b without changing trains. What is R when n is a positive
∗
integer? What is R ?
n
Solution: The relation R contains (a, b) if it is possible to travel from stop a to stop b by making
∗
at most n − 1 changes of trains. The relation R consists of the ordered pairs (a, b) where it is
possible to travel from stop a to stop b making as many changes of trains as necessary. (The
reader should verify these statements.) ▲

EXAMPLE 6 Let R be the relation on the set of all states in the United States that contains (a, b) if state a
n
and state b have a common border. What is R , where n is a positive integer? What is R ?
∗
n
Solution: The relation R consists of the pairs (a, b), where it is possible to go from state a to
∗
state b by crossing exactly n state borders. R consists of the ordered pairs (a, b), where it is
possible to go from state a to state b crossing as many borders as necessary. (The reader should
∗
verify these statements.) The only ordered pairs not in R are those containing states that are not
connected to the continental United States (i.e., those pairs containing Alaska or Hawaii). ▲
Theorem 2 shows that the transitive closure of a relation and the associated connectivity
relation are the same.

THEOREM 2 The transitive closure of a relation R equals the connectivity relation R .
∗

∗
∗
Proof: Note that R contains R by definition. To show that R is the transitive closure of R
∗
∗
we must also show that R is transitive and that R ⊆ S whenever S is a transitive relation that
contains R.
∗
∗
∗
First, we show that R is transitive. If (a, b) ∈ R and (b, c) ∈ R , then there are paths
from a to b and from b to c in R. We obtain a path from a to c by starting with the path
∗
from a to b and following it with the path from b to c. Hence, (a, c) ∈ R . It follows that R is
∗
transitive.
n
Now suppose that S is a transitive relation containing R. Because S is transitive, S also is
n
transitive (the reader should verify this) and S ⊆ S (by Theorem 1 of Section 9.1). Furthermore,
because
∞

∗ k
S = S
k = 1
k
and S ⊆ S, it follows that S ⊆ S. Now note that if R ⊆ S, then R ⊆ S , because any
∗
∗
∗
path in R is also a path in S. Consequently, R ⊆ S ⊆ S. Thus, any transitive relation that
∗
∗
∗
∗
contains R must also contain R . Therefore, R is the transitive closure of R.
Now that we know that the transitive closure equals the connectivity relation, we turn our
attention to the problem of computing this relation. We do not need to examine arbitrarily long
paths to determine whether there is a path between two vertices in a finite directed graph. As
Lemma 1 shows, it is sufficient to examine paths containing no more than n edges, where n is
the number of elements in the set.
LEMMA 1 Let A be a set with n elements, and let R be a relation on A. If there is a path of length at
least one in R from a to b, then there is such a path with length not exceeding n. Moreover,
when a = b, if there is a path of length at least one in R from a to b, then there is such a path
with length not exceeding n − 1.