Mathematical Foundation of Computer Science

DHARM

12 MATHEMATICAL FOUNDATION OF COMPUTER SCIENCE

1.4.3 Pictorial Representation of Relations.................................................................

As shown in the fig. 1.1 (b), a relation can also be represented pictorially by drawing its graph
(directed graph). Consider a relation R be defined between two sets X = {x 1 , x 2 , ........, xl} and Y
= { y 1 , y 2 , ........, ym} i.e., xi Ryj , that is ordered couple (xi, yj) ∈ R where 1 ≤ i ≤ l and 1 ≤ j ≤ m.
The elements of sets X and Y are represented by small circle called nodes. The existence of the
ordered couple such as (xi, yj) is represented by means of an edge marked with an arrow in the
direction from xi to yj, i.e.

xi yj

xRyij

While all nodes related to the ordered couples in R are connected by proper arrows, we

get a directed graph of the relation R. For the ordered couples xi Ryj and yj Rxi we draw two

arcs between nodes xi and yj, i.e.

xi yj

xRyij

yRxji

If ordered couple is like xi Rxi or (xi, xi) ∈ R then we get self loop over the node xi, i.e.

xRxii

xi

From the directed graph of a relation we can easily examine some of its properties. For

example if a relation is reflexive, then we must get a self loop at each node. Conversely if a

relation is irreflexive, then there is no self loop at any node. For symmetric relation if one node

is connected to another, then there must be a return arc from second node to the first node. For

antisymmetric relation there is no such direct return arc exist. Similarly we examine the tran-

sitivity of the relation in the directed graph.

1.4.4 Composite Relation..............................................................................................

When a relation is formed over stages such that let R 1 be one relation defined from set X to Y,

and R 2 be another relation defined from set Y to Z, then a relation R denoted by R 1 ◊ R 2 is a

composite relation, i.e

R = R 1 ◊ R 2 = {(x, z)/for any (x ∈ X, y ∈ Y, z ∈ Z) such that (x, y) ∈ R 1 and (y, z) ∈ R 2 }

Composite relation R can also represented by a diagram shown in Fig 1.5

XYZ

Þ

XY

Fig. 1.5

For example, let R 1 = {(p, q), (r, s), (t, u), (q, s)} and R 2 = {(q, r), (s, v), (u, w)} are two

relations then,

R 1 ◊ R 2 = {(p, r), (r, v), (t, w), (q, v)}, and

R 2 ◊ R 1 = {(q, s)}