B tech. Discrete mathematics (I. T & Comp. Science Engg.) Syllabus

Fig 3
The directed graphs are very important data structures that have applications in Computer Science (in the area of networking).
Definition : Let A, B and C be three sets. Let R be a relation from A to B and S be a relation from B to C. Then, composite relation RS, is a relation from A to C, defined by, a(RS)c, if there is some b  B, such that a R b and b S c.

Example 6: Let A = {1, 2, 3, 4}, B = {a, b, c, d},C = {x, y, z } and let R = {(1, a), (2, d),

(3, a), (3, b), (3, d)} and S = {(b, x), (b, z), (c, y), (d, z)}.

Pictorial representation of the relation in Example 6 can be shown as below (Fig 4).




Fig.4
Thus, from the definition of composite relation and also from Fig 4, RS

will be given as below.

RS = {(2, z), (3, x), (3, z)}.
There is another way of finding composite relation, which is using matrices.
Example7: Consider relations R and S in Example 6. Their matrix representations are as follows.

_1



M  ^{ 0}

R <sub>1

</sub> 0

0 0 0_



0 0 1_

1 0 1^

0 0 0_

_ 0 0 0_

 

_{M  } 1 0 1_

^{S } 0 1 0^

_ 0 0 1_

Consider the product of matrices M_R and M_S as follows: Observe that the non-zero entries in the product tell us which elements are related in RS. Hence, M_RM_S and M_RS have same non-zero entries.

TYPES OF RELATIONS:

In this section, we discuss a number of important types of relations defined from a set

A to itself.