Page 628 - Discrete Mathematics and Its Applications

9.5 Equivalence Relations 607

13. Suppose that the relation R on the finite set A is rep- 25. Use Algorithm 1 to find the transitive closures of these
resented by the matrix M R . Show that the matrix that relations on {1, 2, 3, 4}.
t
represents the symmetric closure of R is M R ∨ M .
R a) {(1, 2), (2,1), (2,3), (3,4), (4,1)}
14. Show that the closure of a relation R with respect to a
b) {(2, 1), (2,3), (3,1), (3,4), (4,1), (4, 3)}
property P, if it exists, is the intersection of all the rela-
c) {(1, 2), (1,3), (1,4), (2,3), (2,4), (3, 4)}
tions with property P that contain R.
d) {(1, 1), (1,4), (2,1), (2,3), (3,1), (3, 2), (3,4), (4, 2)}
15. When is it possible to define the “irreflexive closure”
of a relation R, that is, a relation that contains R,isir- 26. Use Algorithm 1 to find the transitive closures of these
reflexive, and is contained in every irreflexive relation relations on {a, b, c, d, e}.
that contains R? a) {(a, c), (b, d), (c, a), (d, b), (e, d)}
16. Determine whether these sequences of vertices are paths b) {(b, c), (b, e), (c, e), (d, a), (e, b), (e, c)}
in this directed graph. c) {(a, b), (a, c), (a, e), (b, a),(b,c),(c,a),(c,b),(d,a),
a b c
a) a, b, c, e (e, d)}
b) b, e, c, b, e d) {(a, e), (b, a), (b, d),(c,d),(d,a),(d,c),(e,a),(e,b),
c) a, a, b, e, d, e (e, c), (e, e)}
d) b, c, e, d, a, a, b
e) b, c, c, b, e, d, e, d e 27. Use Warshall’s algorithm to find the transitive closures
f) a, a, b, b, c, c, b, e, d d of the relations in Exercise 25.
17. Find all circuits of length three in the directed graph in 28. Use Warshall’s algorithm to find the transitive closures
Exercise 16. of the relations in Exercise 26.
18. Determine whether there is a path in the directed graph in 29. Find the smallest relation containing the relation
Exercise 16 beginning at the first vertex given and ending {(1, 2), (1, 4), (3, 3), (4, 1)} that is
at the second vertex given.
a) reflexive and transitive.
a) a, b b) b, a c) b, b b) symmetric and transitive.
d) a, e e) b, d f) c, d
g) d, d h) e, a i) e, c c) reflexive, symmetric, and transitive.
30. Finish the proof of the case when a = b in Lemma 1.
19. Let R be the relation on the set {1, 2, 3, 4, 5} containing 2.8
the ordered pairs (1, 3), (2, 4), (3, 1), (3, 5), (4, 3), (5, 1), 31. Algorithms have been devised that use O(n ) bit opera-
(5, 2), and (5, 4). Find tions to compute the Boolean product of two n × n zero–
3
2
4
a) R . b) R . c) R . onematrices.Assumingthatthesealgorithmscanbeused,
6
5
d) R . e) R . f) R . give big-O estimates for the number of bit operations us-
∗
ingAlgorithm 1 and usingWarshall’s algorithm to find the
20. Let R be the relation that contains the pair (a, b) if a
and b are cities such that there is a direct non-stop airline transitive closure of a relation on a set with n elements.
flight from a to b. When is (a, b) in ∗ 32. Devise an algorithm using the concept of interior vertices
3
2
a) R ? b) R ? c) R ? in a path to find the length of the shortest path between
∗
two vertices in a directed graph, if such a path exists.
21. Let R be the relation on the set of all students contain-
33. Adapt Algorithm 1 to find the reflexive closure of the
ing the ordered pair (a, b) if a and b are in at least one
common class and a = b. When is (a, b) in transitive closure of a relation on a set with n elements.
2
3
∗
a) R ? b) R ? c) R ? 34. AdaptWarshall’s algorithm to find the reflexive closure of
the transitive closure of a relation on a set with n elements.
22. Suppose that the relation R is reflexive. Show that R is
∗
reflexive. 35. Show that the closure with respect to the property P of
23. Suppose that the relation R is symmetric. Show that R ∗ the relation R ={(0, 0), (0, 1), (1, 1), (2, 2)} on the set
is symmetric. {0, 1, 2} does not exist if P is the property
24. Suppose that the relation R is irreflexive. Is the a) “is not reflexive.”
2
relation R necessarily irreflexive? b) “has an odd number of elements.”
9.5 Equivalence Relations
Introduction
In some programming languages the names of variables can contain an unlimited number of
characters. However, there is a limit on the number of characters that are checked when a
compiler determines whether two variables are equal. For instance, in traditional C, only the
first eight characters of a variable name are checked by the compiler. (These characters are