Page 627 - Discrete Mathematics and Its Applications

606 9 / Relations

[k]
LEMMA 2 Let W k =[w ] be the zero–one matrix that hasa1inits (i, j)th position if and only if there
ij
is a path from v i to v j with interior vertices from the set {v 1 , v 2 ,..., v k }. Then
w [k] = w [k−1] ∨ (w [k−1] ∧ w [k−1] ),
ij ij ik kj
whenever i, j, and k are positive integers not exceeding n.

Lemma 2 gives us the means to compute efficiently the matrices W k ,k = 1, 2,...,n.We
display the pseudocode for Warshall’s algorithm, using Lemma 2, as Algorithm 2.

ALGORITHM 2 Warshall Algorithm.

procedure Warshall (M R : n × n zero–one matrix)
W := M R
for k := 1 to n
for i := 1 to n
for j := 1 to n
w ij := w ij ∨ (w ik ∧ w kj )
return W{W =[w ij ] is M R }
∗

The computational complexity of Warshall’s algorithm can easily be computed in terms of
bit operations. To find the entry w [k] from the entries w [k−1] , w [k−1] , and w [k−1] using Lemma
ij ij ik kj
2
2 requires two bit operations. To find all n entries of W k from those of W k−1 requires 2n 2
bit operations. Because Warshall’s algorithm begins with W 0 = M R and computes the se-
quence of n zero–one matrices W 1 , W 2 ,..., W n = M R , the total number of bit operations used
∗
3
2
is n · 2n = 2n .
Exercises
1. Let R be the relation on the set {0, 1, 2, 3} containing 7.
the ordered pairs (0, 1), (1, 1), (1, 2), (2, 0), (2, 2), and a b
(3, 0). Find the
a) reflexive closure of R. b) symmetric closure of R.
2. Let R be the relation {(a, b) | a = b} on the set of inte-
gers. What is the reflexive closure of R?
3. Let R be the relation {(a, b) | a divides b} on the set of
integers. What is the symmetric closure of R? c d
4. How can the directed graph representing the reflexive clo- 8. How can the directed graph representing the symmetric
sure of a relation on a finite set be constructed from the closure of a relation on a finite set be constructed from
directed graph of the relation? the directed graph for this relation?
In Exercises 5–7 draw the directed graph of the reflexive clo- 9. Find the directed graphs of the symmetric closures of the
sure of the relations with the directed graph shown. relations with directed graphs shown in Exercises 5–7.
5. 6. 10. Find the smallest relation containing the relation in Ex-
a b
a b ample 2 that is both reflexive and symmetric.
11. Find the directed graph of the smallest relation that is
both reflexive and symmetric that contains each of the
relations with directed graphs shown in Exercises 5–7.
12. Suppose that the relation R on the finite set A is rep-
resented by the matrix M R . Show that the matrix that
c d
c d represents the reflexive closure of R is M R ∨ I n .