Discrete Mathematical Structures by Pearson

3-38 Discrete Mathematical Structures

Example 1 Using Warshall’s algorithm, find the transitive closure R

∞

of the relation R = {(1, 2),

(2, 2), (2, 3), (3, 3)} on the set A = {1, 2 ,3}

Solution: The matrix of R is

W

0

= M

R

=

010

011

001





















(1) To compute W

1

so that

K =1

(i.e., column 1)

(i) Transfer all 1’s from W

0

to W

1

.

(ii) Non-zero entries in column 1 are none and non-zero entries in row 1 are at location 2.

Hence, no new entry. Hence, W

1

= W

0

=

010

011

001





















(2) To compute W

2

so that K = 2 (i.e., column 2)

(i) Transfer all 1’s from W

1

to W

2.

(ii) Non-zero entries in column 2 are in locations 1 and 2 and non-zero entries in row 2 are

at locations 2 and 3.

Hence,

W

2

has 1 in positions (1, 2), (1, 3), (2, 2), (2, 3).

∴ W