Page 618 - Discrete Mathematics and Its Applications

9.4 Closures of Relations 597

16. Let R be a relation on a set A with n elements. If there 27. 28.
are k nonzero entries in M R , the matrix representing R, a b
how many nonzero entries are there in M −1, the matrix b
R
representing R −1 , the inverse of R?
17. Let R be a relation on a set A with n elements. If there
are k nonzero entries in M R , the matrix representing R,
how many nonzero entries are there in M , the matrix
R c d c d
representing R, the complement of R? 29. How can the directed graph of a relation R on a finite
18. Draw the directed graphs representing each of the rela- set A be used to determine whether a relation is asym-
tions from Exercise 1. metric?
19. Draw the directed graphs representing each of the rela-
tions from Exercise 2. 30. How can the directed graph of a relation R on a finite
20. Draw the directed graph representing each of the relations set A be used to determine whether a relation is irreflex-
from Exercise 3. ive?
21. Draw the directed graph representing each of the relations 31. Determine whether the relations represented by the di-
from Exercise 4. rected graphs shown in Exercises 23–25 are reflexive,
22. Draw the directed graph that represents the relation irreflexive, symmetric, antisymmetric, and/or transitive.
{(a, a), (a, b), (b, c), (c, b), (c, d), (d, a), (d, b)}. 32. Determine whether the relations represented by the di-
In Exercises 23–28 list the ordered pairs in the relations rep- rected graphs shown in Exercises 26–28 are reflexive, ir-
resented by the directed graphs. reflexive, symmetric, antisymmetric, asymmetric, and/or
23. 24. transitive.
a
a
33. Let R be a relation on a set A. Explain how to use the di-
rected graph representing R to obtain the directed graph
representing the inverse relation R −1 .
34. Let R be a relation on a set A. Explain how to use the di-
b c b c rected graph representing R to obtain the directed graph
25. 26. representing the complementary relation R.
a b a b
35. Show that if M R is the matrix representing the relation R,
n
then M [n] is the matrix representing the relation R .
R
36. Given the directed graphs representing two relations, how
can the directed graph of the union, intersection, sym-
c d metric difference, difference, and composition of these
c d relations be found?

9.4 Closures of Relations

Introduction

A computer network has data centers in Boston, Chicago, Denver, Detroit, New York, and San
Diego. There are direct, one-way telephone lines from Boston to Chicago, from Boston to
Detroit, from Chicago to Detroit, from Detroit to Denver, and from New York to San Diego.
Let R be the relation containing (a, b) if there is a telephone line from the data center in a to
that in b. How can we determine if there is some (possibly indirect) link composed of one or
more telephone lines from one center to another? Because not all links are direct, such as the
link from Boston to Denver that goes through Detroit, R cannot be used directly to answer this.
In the language of relations, R is not transitive, so it does not contain all the pairs that can be
linked. As we will show in this section, we can find all pairs of data centers that have a link
by constructing a transitive relation S containing R such that S is a subset of every transitive
relation containing R. Here, S is the smallest transitive relation that contains R. This relation is
called the transitive closure of R.
In general, let R be a relation on a set A. R may or may not have some property P, such as
reflexivity, symmetry, or transitivity. If there is a relation S with property P containing R such
that S is a subset of every relation with property P containing R, then S is called the closure