ICS 241: Discrete Mathematics II (Spring 2015)

9.4 Closure of Relations

Reflexive Closure
The reflexive closure of a relation R on A is obtained by adding (a, a) to R for each a ∈ A.

Symmetric Closure
The symmetric closure of R is obtained by adding (b, a) to R for each (a, b) ∈ R.

Transitive Closure
The transitive closure of R is obtained by repeatedly adding (a, c) to R for each (a, b) ∈ R and
(b, c) ∈ R.

Paths and Circuits in Directed Graphs

A path from a to b in the directed graph G is a sequence of edges (x0 , x1 ), (x1 , x2 ), (x2 , x3 ),
. . . , (xn−1 , xn ) in G, where n is a nonnegative integer, and x0 = a and xn = 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 x0 , x1 , x2 , . . . , xn−1 , xn 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.

Path in a Relation
Theorem 1: Let R be a relation on a set A. There is a path of length n, where n is a positive
integer, from a to b if and only if (a, b) ∈ Rn .

Connectivity Relation A.K.A. Transitive Closures

Let R be a relation on a set A. The connectivity relation R∗ consists of the pairs (a, b) such that
there is a path of length at least one from a to b in R.
In other words: ∞
[
∗
R = Rn
n=1

where Rn consists of the pairs (a, b) such that there is a path of length n from a to b.

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

Theorem 3: Let MR be the zero-one matrix of the relation R on a set with n elements. Then the
zero-one matrix of the transitive closure R∗ is
[2] [3] [n]
MR∗ = MR ∨ MR ∨ MR ∨ . . . ∨ MR

1
ICS 241: Discrete Mathematics II (Spring 2015)

Simple Algorithm for Computing Transitive Closure

This algorithm shows how to compute the transitive closure. Runs in O(n4 ) bit operations.

Algorithm transitive closure(MR : zero-one n × n matrix)

A = MR
B=A
for i = 2 to n do
A = A  MR
B =B∨A
end for
return B{B is the zero-one matrix for R∗ }

Warshall’s Algorithm
Warhsall’s algorithm is a faster way to compute transitive closure. Runs in O(n3 ) bit operations.

Algorithm W arshall(MR : zero-one n × n matrix)

W = MR
for k = 1 to n do
for i = 1 to n do
for j = 1 to n do
wij = wij ∨ (wik ∧ wkj )
end for
end for
end for
return W {W = [wij ] is the zero-one matrix for R∗ }

9.4 pg. 607 # 1

Let R be the relation on the set {0, 1, 2, 3} containing the ordered pairs (0, 1), (1, 1), (1, 2), (2, 0), (2, 2), (3, 0).
Find the

a) reflexive closure of R
We need to add (a, a) in R to make a reflexive closure.
{(0, 0), (0, 1), (1, 1), (1, 2), (2, 0), (2, 2), (3, 0), (3, 3)}

b) symmetric closure of R
We need to add (b, a) for each (a, b) in R to make a symmetric closure.
{(0, 1), (0, 2), (0, 3), (1, 0), (1, 1), (1, 2), (2, 0), (2, 1), (2, 2), (3, 0)}

2
ICS 241: Discrete Mathematics II (Spring 2015)

9.4 pg. 607 # 5

For the directed graph shown

a b

c d

a) Find the reflexive closure

a b

c d

b) Find the symmetric closure

a b

c d

9.4 pg. 608 # 25

Use Algorithm 1 to find the transitive closure of these relations on {1, 2, 3, 4}.

a) {(1, 2), (2, 1), (2, 3), (3, 4), (4, 1)}
Transitive Closure
=MR∗
[2] [3] [4]
= MR ∨ MR ∨ MR ∨ MR

3
ICS 241: Discrete Mathematics II (Spring 2015)

         
0 1 0 0 1 0 1 0 0 1 0 1 1 0 1 0 1 1 1 1
1 0 1 0 0
  1 0 1 1
  0 1 0 0
  1 0 1 1
  1 1 1
=
0 ∨ ∨ ∨ = 
0 0 1 1 0 0 0 0 1 0 0 1 0 1 0 1 1 1 1
1 0 0 0 0 1 0 0 1 0 1 0 0 1 0 1 1 1 1 1

b) {(2, 1), (2, 3), (3, 1), (3, 4), (4, 1), (4, 3)}
Transitive Closure
=MR∗
[2] [3] [4]
= MR ∨ MR ∨ MR ∨ MR
         
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 0 1 0 1
  0 0 1 1
  0 1 0 1
  0 0 1 1
  0 1 1
=
1 ∨ ∨ ∨ = 
0 0 1 1 0 1 0 1 0 0 1 1 0 1 0 1 0 1 1
1 0 1 0 1 0 0 1 1 0 1 0 1 0 0 1 1 0 1 1

9.4 pg. 608 # 27

Use Warshall’s algorithm to find the transitive closure of these relations on {1, 2, 3, 4}.

a) {(1, 2), (2, 1), (2, 3), (3, 4), (4, 1)}
       
0 1 0 0 0 1 0 0 1 1 1 0 1 1 1 1
1 0 1 0 1 1 1 0
  1 1 1 0
 1 1 1 1
W0 =  0 0 0 1 W1 = 0 W =  W = 
1 2 1 3
  
0 0 0 0 0 0 0 0 1
1 0 0 0 1 1 0 0 1 1 1 0 1 1 1 1
 
1 1 1 1
1 1 1 1
W4 =  1 1 1 1


1 1 1 1

b) {(2, 1), (2, 3), (3, 1), (3, 4), (4, 1), (4, 3)}
       
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 0 1 0 1 0 1 0
  1 0 1 0
 1 0 1 1
W0 =  1 0 0 1 W1 = 1 0 0
  W2 =  W3 =  
1  1 0 0 1 1 0 0 1
1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 1
 
0 0 0 0
1 0 1 1
W4 =  1 0 1 1


1 0 1 1