Discrete Mathematics

148 DISCRETE

MATHEMATIC·"'--------------------------

Example 19 Let A =

{I,

2, 3, 4} and let R = { (1, 2), (2, 3), (3, 4 ), (2, l)}, find the transitive closure

of

R.

I solution I

The digraph

of

R

Since

/?'"

is the transitive closure, we can proceed geometrically by computing all paths.

From vertex 1 we have paths to vertices

2,

3, 4, and

1.

Note that the path from 1 to 1 proceeds from 1 to 2 to

1.

Thus, we see that the ordered pairs (1, 1),

(1, 2),

(1, 3), and (1, 4) are in/?'".

Starting from vertex

2,

we have paths to vertices

2,

1,

3,

4. So ordered pairs (2,

1)

, (2, 2),

(2

, 3), (2, 4)

are

in/?'".

The only other path is from vertex