Faculty of IT & CS == Discrete Mathematics - Relations == Spring 2020 - Prof.

Reda S Tantawi

Relations
In this chapter we discuss the mathematics of relations defined on sets.
The Cartesian Product
For any two sets A and B, we can form their Cartesian product A  B (read “ A cross B ”) in
accordance with the following definition, for all x A and yB :
A  B = ( x, y ): x A , y B .

It is obvious that the Cartesian product of two sets is a set of ordered-pairs of all the elements
of the two sets.
For examples:
If A=  1, 2,3 and B =  a, b, c, d  then we have:

A  B = (1, a ),(1, b),(1, c),(1, d ),(2, a ),(2, b),(2, c),(2, d ), (3, a ),(3, b),(3, c),(3, d ) ,

B  A = (a,1),(a,2),(a,3),(b,1),(b,2),(b,3),(c,1),(c,2),(c,3),(d ,1),(d ,2),(d ,3) ,

A  A = A2 =(1,1),(1,2),(1,3),(2,1),(2,2),(2,3),(3,1),(3,2),(3,3) ,

B  B = B2 =(a, a),(a, b),(a, c),(a, d ),(b, a),(b, b),(b, c),(b, d ),(c, a),(c, b),(c, c),(c, d ),

(d , a ),(d , b),(d , c),(d , d )

Definition of a relation
Any subset of the Cartesian product A  B defines a relation from the set A to the set B
and is denoted by R , i. e.; R  A  B . We say x is related to y , where x A and yB , if
( x, y ) R . It is called a binary relation ‫ عالقة ثنائية‬because it is a subset of a Cartesian product
of two sets. The ordered-pair ( x, y ) R means that x is related to y according to this relation
and can be written as x R y .

For examples:
The following are relations from A=  1, 2,3 to B =  a, b, c, d 
R1 = (1, a ),(1, d ),(2, a),(3, d ) ,

R2 = (2, b),(2, c),(2, d ),(3, a) ,

R3 = (1, a ),(1, b),(1, c),(1, d ),(2, a),(2, b),(2, c),(2, d ), (3, a ),(3, b),(3, c ),(3, d ) ,

R4 = (2, b) .

35
Faculty of IT & CS == Discrete Mathematics - Relations == Spring 2020 - Prof. Reda S Tantawi

If R  A  A ( R  A2 ) we say that R is a relation on the set A .

For examples:
The following are relations on A=  1, 2,3

R5 = (1,1),(1, 2),(2, 2) ,

R6 = (2,1),(2,3),(3,1),(3,3) ,

R7 = (1,1),(1,2),(1,3),(2,1),(2,2),(2,3),(3,1),(3,2),(3,3) ,

and the following are relations on B =  a, b, c, d 

R8 = (a, a ),(b, b),(d , d ) ,

R9 = (b, a ),(b, c),(c, d ),( d , a) ,

R10 = (b, b),(d , d ) .

If R is a relation R from the set A to the set B , we can define the domain ‫مدى‬, range
‫نطاق‬, and field ‫ مجال‬of the relation as following:
The domain of a relation: the domain of the relation R is the set  x :( x, y ) R .

The range of a relation: the range of the relation R is the set  y :( x, y ) R .

The field of a relation: the field of the relation R is the set given by union of the domain
and the range of the relation.
For examples:
- The relation R2 has the domain 2,3 , the range a, b, c, d  , and the field 2,3, a, b, c, d  .

- The relation R6 has the domain 2,3 , the range 1,3 , and the field 1, 2,3 .

Exercises:
Find the domain, range, and field of the above relations R1, R4 , R7 , and R8 .

In the above we defined the relation as a set, which is the usual representation or the
explicit form of the relation. In the following we are going to introduce the Boolean matrix
and graphical representations of a relation.

36
Faculty of IT & CS == Discrete Mathematics - Relations == Spring 2020 - Prof. Reda S Tantawi

Boolean Matrix Representation

We can represent any relation R from a set A having m elements to a set B having n
elements by an m  n matrix M R , where the elements of A indicate to the rows of the matrix.
This matrix associated with a relation R can be constructed by putting “1” for the ordered-
pairs ( x, y ) R and putting “0” for the ordered-pairs ( x, y ) R .

For examples:
The Boolean matrix associated with the above relations R1, R2 , R6 , and R8 are

1 0 0 1  0 0 0 0 
   
M R1 = 1 0 0 0 , M R2 = 0 1 1 1 
   
 0 0 0 1  1 0 0 0 
1 0 0 0 
0 0 0   
  0 1 0 0 
M R6 = 1 0 1  , M R8 = 
   0 0 0 0 
1 0 1  0 0 0 1 
 

Exercises:
1. Write down the Boolean matrix associated with the relations R1, R2 , and R3 defined from

A=  1, 2,3, 4 to B =  a, b, c, d  such that:

R1 = (1, a),(1, c),(2, d ),(3, a),(3, d ),(4, d ) .

R2 = (1, d ),(2, c),(2, d ),(3, a),(3, b),(4, a),(4, b),(4, c) .

R3 = (1, c),(2, a),(2, b),(2, d ),(3, d ),(4, b),(4, d ) ,

2. Write down the Boolean matrix associated with the relations R4 , and R5 defined on

B =  a, b, c, d  such that:

R4 = (a, a),(a, c),( a, d ),(b, a),(b, d ),(c, a),(c, c),( d , c),( d , d ) ,

R5 = (a, b),(a, c),(b, c),(b, d ),(c, c),(c, d ),(d , a),(d , b) ,

37
Faculty of IT & CS == Discrete Mathematics - Relations == Spring 2020 - Prof. Reda S Tantawi

Also, we can find the explicit form of a relation if the corresponding Boolean matrix is given.
For examples
1 0 0 0
1 0 0 0
1. The relation R on A = a, b, c, d  whose Boolean matrix M R =   is
1 1 0 0
0 0
 1 1
R = (a, a), (b, a), (c, a), (c, b), ((d , b), (d , c)

1 0 0 1 1 
 
1 0 1 0 0
 
2. The relation R on A = a, b, c, d , e whose Boolean matrix M R = 1 1 0 0 1  is
0 1 1 1 0 

1 0 0 1 0 

R = (a, a ),(a, d ),(a, e),(b, a),(b, c),(c, a),(c, b),(c, e),(d , b),(d , c), (d , d ),(e, a ),(e, d )

Exercises:
1. Write down the relation defined on A =  a, b, c, d  whose Boolean matrix is

0 1 1 0 0 0 0 0
1 0 1 0 0 1 1 0
(i) M R1 =   (ii) M R2 =  
0 1 0 1 0 1 0 1
   
1 0 1 1 1 0 1 1

2. Write down the relation defined on A= 1,2,3,4,5 whose Boolean matrix is

1 0 1 0 1  1 0 0 0 0 
   
1 0 1 0 1   0 1 1 0 1 
   
(i) M R1 = 0 1 0 1 0 (ii) M R2 = 0 0 1 1 1 
1 0 1 1 1  1 0 1 1 0 
  
0 0 0 1 0  0 1 0 1 1 
  

38
Faculty of IT & CS == Discrete Mathematics - Relations == Spring 2020 - Prof. Reda S Tantawi

Graphical Representation
Any relation R on a set A can be represented graphically, by placing the elements of A
in a closed curve and joining the elements x and y in each ordered-pair ( x, y ) R by directed
arc which can be curve or an arrow starting at the element x and ending at the element y .
The elements of A appear in R are called vertices or nodes and each curve is called an edge,
where the curve from an element to itself (i. e.; ( x, x) R ) is called a self-loop. The graphical
representation of a relation is called directed graph (or digraph) of the relation.

The out-degree of a vertex x is the number of edges out of it and is denoted by d + ( x) . The

in-degree of a vertex x is the number of edges going into it and is denoted by d − ( x) .

For examples
Show the digraph of the relations R1 , and R2 on B =  a, b, c, d , e, f  such that:

R1 = (a, a),(a, c),(b, d ),(b, f ),( f , a ),( f , c),( f , d ),( f , f ) ,

R2 = (a, a),(a, b),(b, a),(b, b),(b, c),(c, a),(c, e),(c, f ),(e, f ) .

Solution

Digraph of R1
It is easy to note that,
d + (a) = 2, d − (a) = 2, d + (b) = 2, d − (b) = 0, d + (c) = 0, d − (c) = 2, d + (d ) = 2, d − (d ) = 2,
d + (e) = 0, d − (e) = 0, d + ( f ) = 4, d − ( f ) = 2 .

39
Faculty of IT & CS == Discrete Mathematics - Relations == Spring 2020 - Prof. Reda S Tantawi

Digraph of R2
It is easy to note that,

d + (a) = 2, d − (a) = 3, d + (b) = 2, d − (b) = 2, d + (c) = 3, d − (c) =1, d + ( d ) = 0, d − ( d ) = 0,

d + (e) =1, d − (e) =1, d + ( f ) =1, d − ( f ) =1 .

Exercises:
1. Show the digraph of the relations R1 , and R2 on A =  a, b, c, d , e, f  such that:
R1 = (a, a),(a, f ),(b, a),(b, d ),(c, a),(c, c),( d , c),( f , b) ,

R2 = (a, c),(a, f ),(b, a),(b, c),(b, f ),(c, a),(c, d ),(c, f ),(e, f ),( d , f ) ,

and find the in- and out-degrees of each node.

2. Show the digraph of the relations R1 , and R2 on B =  1,2,3,4,5 such that:
R1 = (1,3),(1,5),(2,2),(2,4),(3,1),(3,2),(4,2),(4,3),(4,5),(5,3),(5,4) ,

R1 = (1,1),(1,2),(2,3),(2,4),(3,2),(3,5),(4,2),(4,4),(4,5),(5,2),(5,3),(5,4) ,

and find the in- and out-degrees of each node.

40
Faculty of IT & CS == Discrete Mathematics - Relations == Spring 2020 - Prof. Reda S Tantawi

Some types of relations on a set

Let R be a relation on a set A .
1. The relation R is a reflexive on A if, and only if, ( x, x) R for all x A . That is, each
element in A is related to itself.
2. The relation R is a symmetric on A if, and only if, ( x, y ) R then ( y, x) R for all
x, y A
3. The relation R is a transitive on A if, and only if, ( x, y ),( y, z )  R then ( x, z )R for
all x , y, z  A .
4. R is not reflexive on A if, and only if, there is an element x in A such that ( x, x) R .
5. R is not symmetric on A if, and only if, there are elements x and y in A such that
( x, y ) R but ( y, x)R .
6. R is not transitive on A if, and only if, there are elements x, y and z in A such that
( x, y ),
( y, z )  R but ( x, z )R .
7. R is irreflexive if, and only if, for all x A , ( x, x) R . That is, no element in A is related to
itself.
8. R is asymmetric if, and only if, ( x, y ) R but ( y, x) R for all x, y A .
9. A relation on a set that satisfies the three properties of reflexivity, symmetry, and
transitivity (no. 1, 2, and 3) is called an equivalence relation.

Examples
1. Determine the types of the following relation defined on A =  a, b, c, d , e, f  relative to

reflexivity, symmetry, or transitivity (write the reasons):

R = (a, a),(a, b),( a, f ),( a, e),(b, b),(b, c), (c, d ),(c, f ),( d , a),( d , f ), (e, f ),( f , c )

Solution:
Since (c, c) R then R is not reflexive, and it is not irreflexive because (a, a),(b, b)R .
Since (a, b)R but (b, a)R then R is not symmetric, and it is not asymmetric because
(a, c),(c, a) R . Since (a, b),(b, c)R, (a, c)R then R is not transitive.
41
Faculty of IT & CS == Discrete Mathematics - Relations == Spring 2020 - Prof. Reda S Tantawi

2. Determine the types of the following relation defined on A =  a, b, c, d , e, f  relative to

reflexivity, symmetry, or transitivity (write the reasons):

R1 = (a, a),(a, c),(b, b),(c, c), (c, a),( d , e),(e, f )

R2 = (a, a ),(a, c),(a, d ),(b, b),(c, d ), (c, a),( d , e),(e, d )

Solution:
- The relation R1 is not reflexive because (d , d )R1 , and it is not irreflexive because

(a, a)R1 . The relation R1 is not symmetric because (d , e)R1 but (e, d )R1 , and it is not

asymmetric because (a, b),(b, a)R . Finally, it is not transitive because (d , e),(e, f )R1 but
(d , f )R1 .

- The relation R2 is not reflexive because (d , d ) R1 , and it is not irreflexive because

(a, a)R1 . The relation R2 is not symmetric because (c, d )R1 but (d , c)R1 , and it is not

asymmetric because (a, b),(b, a)R . Finally, it is not transitive because (d , e), (e, f )R1 but

(d , f )R1 .

42
Faculty of IT & CS == Discrete Mathematics - Relations == Spring 2020 - Prof. Reda S Tantawi

Exercises:
1. Determine the types of the following relations defined on A=  0,1,2,3 relative to

reflexivity, symmetry, or transitivity (write the reasons):

R1 = (0,0),(0,1),(0,3),(1,1), (1,0),(2,3),(3,3)
,
R2 = (0,0),(0,1),(1,1),(1,2), (2,2),(2,3)
,
R3 = (2,3),(3,2) ,

R4 = (1,2),(2,1),(1,3),(3,1)
,
R5 = (0,0),(0,1),(0,2),(1,2)
.

2. Determine the types of the relation

R = (a, a),(a, b),(a, c),(b, a),(b, b),(b, c), (c, a),(c, b),(c, c),( d , d ), (d , e),(e, d ),(e, e),( f , f )

defined on B =  a, b, c, d , e, f  relative to reflexivity, symmetry, or transitivity (write the

reasons).

43
Faculty of IT & CS == Discrete Mathematics - Relations == Spring 2020 - Prof. Reda S Tantawi

Closure Relations
Let R be a relation on a set A and R needs to be augmented with some elements so that
the new relation satisfies the property of reflexivity, symmetry, transitivity, or equivalency.
The smallest set containing R and satisfying a certain property is called a closure relation
relative to this property and is denoted by Rc .

Examples:
1. If the relation R on the set A =  a, b, c, d , e, f  is defined as:

R = (a, a),(a, b),( a, f ),( a, e),(b, b),(b, c), (c, d ),(c, f ),( d , a),( d , f ), (e, f ),( f , c )

Find the closure relations of R with respect to reflexivity, symmetry, and transitivity.
Solution:
The closure relations of R with respect to reflexivity is

Rc =(a, a),(a, b),(a, f ),(a, e),(b, b),(b, c), (c, d ),(c, f ),(d , a),(d , f ),(e, f ),( f , c),(c, c),

(d , d ),(e, e),( f , f )

The closure relations of R with respect to symmetry is

Rc =(a, a),(a, b),(a, f ),(a, e),(b, b),(b, c),(c, d ),(c, f ),(d , a),(d , f ),(e, f ),( f , c),(b, a),
( f , a),(e, a),(c, b),( d , c),( a, d ),( f , d ),( f , e)

The closure relations of R with respect to transitivity is

Rc =(a, a),(a, b),(a, f ),(a, e),(b, b),(b, c),(c, d ),(c, f ),(d , a),(d , f ),(e, f ),( f , c),(a, c),(b, d ),

(b, f ),(c, a),(d , b),(d , e),(d , c),(e, c),( f , d ),(b, a),( a, d ),(b, e), (c, b ),(c, e)

2. If the relation R on the set A =  a, b, c, d , e, f  is defined as:

R = (a, b),(a, f ),(a, e),(b, b),(b, c), (c, f ),( d , a),( d , f ), ( f , c)

Find the closure relations of R with respect to reflexivity, symmetry, transitivity, and
equivalency.
Solution:
The closure relations of R with respect to reflexivity is

44
Faculty of IT & CS == Discrete Mathematics - Relations == Spring 2020 - Prof. Reda S Tantawi

Rc1 =(a, b),(a, f ),(a, e),(b, b),(b, c),(c, f ),(d , a),(d , f ),( f , c),(a, a),(c, c), (d , d ),(e, e),( f , f )
The closure relations of R with respect to symmetry is

Rc2 =(a, b),(a, f ),(a, e),(b, b),(b, c),(c, f ),(d , a),(d , f ),( f , c),(b, a),( f , a),(e, a),(c, b),

(a, d ),( f , d )
The closure relations of R with respect to transitivity is

Rc3 =(a, b),(a, f ),(a, e),(b, b),(b, c),(c, f ),(d , a),(d , f ),( f , c),(a, c),(b, f ),(d , b),(d , e),(d , c)
The closure relations of R with respect to equivalency is

Rc4 = Rc1  Rc2  Rc3 = Rc2 =(a, b),(a, f ),(a, e),(b, b),(b, c),(c, f ),(d , a),(d , f ),( f , c),(a, a),

(c, c),(d , d ),(e, e),( f , f ),(b, a),( f , a),(e, a),(c, b),( a, d ),( f , d ), (a, c ),(b, f ),(d , b),(d , e),(d , c )

3. If the relation R on the set A =  a, b, c, d , e, f  is defined as:

R = (a, a ),(a, c),(b, b),(b, f ),(c, a),(c, c),( d , e),(e, f )

Find the closure relations of R with respect to reflexivity, symmetry, transitivity, and
equivalency.
Solution:
The closure relation of R with respect to reflexivity is:

R 1 = (a, a) , (a, c), (b, b), (b, f ), (c, a), (c, c), (d , d ), (d , e), (e, e), (e, f ), ( f , f )
c

The closure relation of R with respect symmetry is:

Rc2 =(a, a),(a, c),(c, a),(b, b),(b, f ),( f , b),(c, c),(d , e),(e, d ),(e, f ),( f , e)
The closure relation of R with respect transitivity is:

Rc3 =(a, a),(a, c),(b, b),(b, f ),(c, a),(c, c),(d , e),(e, f ),(d , f )

45
Faculty of IT & CS == Discrete Mathematics - Relations == Spring 2020 - Prof. Reda S Tantawi

Exercises:
1. If the relations R1 and R2 are defined on the set A =  a, b, c, d  as:

R1 = (a, b),(a, c),(b, c),(c, d )

R2 = (a, a),(a, b),(a, c),(b, a),(b, b),(c, c)

Find the closure relations of R with respect to reflexivity, symmetry, transitivity and
equivalency.

2. If the relations R1 and R2 are defined on the set B =  a, b, c, d , e as:

R1 = (a, a ),(a, b),(b, c),(b, d ),(c, d ),(c, e),( d , b),( d , c),(e, a)

R2 = (a, e),(b, b),(c, c),( d , d ),(e, a)

Find the closure relations of R with respect to reflexivity, symmetry, transitivity and
equivalency.

3. If the relations R1 and R2 are defined on the set A=  0,1,2,3 as:

R1 = (0,0),(0,1),(0,3),(1,1), (1,0),(2,3),(3,3)
,
R2 = (0,0),(0,1),(1,1),(1,2), (2,2),(2,3)
,
R3 = (2,3),(3, 2) ,

Find the closure relations of R with respect to reflexivity, symmetry, transitivity and
equivalency.

46
Faculty of IT & CS == Discrete Mathematics - Relations == Spring 2020 - Prof. Reda S Tantawi

Paths of a relation on a set

Let R be a relation on a set A such that
a R x1, x1 R x2 , x2 R x3, , xn Rb .

We can define a path from the vertex a to the vertex b as the sequence:
 = ( a , x1, x2 , x3 , , xn , b )

The length of the path is the number of edges between the elements of  which equals the
number of vertices in the path minus 1.
If the path starts and ends at the same vertex, it is called a cycle. Every self-loop represents a
path of length 1.
Note that: The best way to determine the paths of a relation is to draw the digraph of the
relation where,
1. It is better to us arrows as directed arcs between the vertices.
2. A path can always be “trimmed” in such a way that every vertex is visited at most
once, except cycles where the starting and ending vertices are the same.
3. No path should be a subpath of another.

Examples:
1. The digraph of the relation R = (a, c),(a, f ),(b, a),(b, e),(c, b),( d , c),( f , d ),(c, c) defined
On the set A =  a, b, c, d , e, f  is

The paths are 1 = (c, c),  2 = (b, a, f , d , c, b),  3 = (b, a, c, b),  4 = (b, e) .

47
Faculty of IT & CS == Discrete Mathematics - Relations == Spring 2020 - Prof. Reda S Tantawi

2. The digraph of the relation R = (a, b),(a, f ),(b, c),(b, e), (c, d ),(d , a),( d , f ),(e, f ),( f , c)

defined on the set A = a, b, c, d , e, f  is:

The paths are 1 = c, d , a, b, c,  2 = c, d , a, f , c ,  3 = c, d , f , c,  4 = c, d , a, b, e, f , c

3. The graph of the relation R =(a, b),(b, b),(b, c),(b, d ),(b, e),(d , c),(e, a),(e, d ) defined on the set

A = a, b, c, d , e is:

The paths of a relation R are:

1 = (a, b, c), 2 = (a, b, d , c), 3 = (a, b, e, d , c), 4 = (a, b, e, a), 5 = (b, b)

48
Faculty of IT & CS == Discrete Mathematics - Relations == Spring 2020 - Prof. Reda S Tantawi

Exercises:
Find the paths of the following relations defined on the set A= 1,2,3,4,5,6 such that:

R1 = (1,2),(2,3),(3,3),(3,4),(4,3),(4,1),(4,5),(6,1),(6,4)

R2 = (1,1),(1,2),(2,1),(2,2),(2,3),(2,4),(3,4),(4,2)

R3 = (1,2),(2,4),(2,5),(3,1),(4,3),(4,6),(5,3),(6,1)

R4 = (1,2),(1,3),(1,4),(1,5),(2,3),(2,4),(5,2),(5,3)

49
Faculty of IT & CS == Discrete Mathematics - Relations == Spring 2020 - Prof. Reda S Tantawi

Trees
A relation R on a finite set A is called a tree if there is one vertex only x0 such that

d + ( x0 )  0, d − ( x0 ) = 0 , and d − ( xi ) =1 for every other vertex xi in R . The vertex x0 is called

the root of the tree and the tree is called rooted tree denoted by T = ( R, x0 ) . The best way to
verify that a relation is a tree or not, we should draw the digraph of the relation starting with
the root at the top and use arrows for all the edges, as we will see in the lecture. The vertices
of a tree that have zero out-degree are called leaves.

Tree structure
The structure of a rooted tree T = ( R, x0 ) consists of levels. The root x0 said to be at
“level 0” and the level of any other vertex is the number of edges along the unique path
between it and the root. The height of a rooted tree is the maximum level of any vertex of the
tree. The vertices that are adjacent to a vertex xi and are one level farther away from the root

are called children of xi , where xi is called the parent of them.

Remarks:
1. Any rooted tree on a set is irreflexive, asymmetric, and not transitive.
2. The number of paths of a tree equals the number of leaves.

Binary trees
A binary tree is a rooted tree in which every parent has at most two children. Each child in
a binary tree is designated either a left child or a right child (but not both), and every parent
has at most one left child and one right child. A full binary tree is a binary tree in which each
parent has exactly two children.

Subtrees
The tree with a root xk that results from the tree T = ( R, x0 ) by deleting all the paths that

do not begin at xk is called subtree of the tree T and is denote by T( xk ) .

50
Faculty of IT & CS == Discrete Mathematics - Relations == Spring 2020 - Prof. Reda S Tantawi

Examples
1. Let R be a relation on the set A = b, c, d , e, f , g , h, i, j , k  such that:

R = (c, d ),(c, b),(e, c),(e, f ),(e, g ), ( f , i),( g , h),(h, i),( h, k )

The graph of the relation is:

The digraph shows that T = ( R, e) is a tree (not binary ) and of leaves i, k , f , b, d  . It is seen

that, for example, f , g , c are children of e , k and j are the left and right children of h
respectively.

We can obtain many subtrees of T = ( R, k ) , for example:

T( f ) T (g) T (h) T (c )

51
Faculty of IT & CS == Discrete Mathematics - Relations == Spring 2020 - Prof. Reda S Tantawi

2. Let R be a relation on the set A = a, b, c, d , e, f , g , h, i, j , k , l , m such that:

R = ( g , b),( g , l ),(h, c),(h, j ), (i, d ),(i, e),( j, a),( j, i),( k , h),( k , m), (m, f ),(m, g )

The graph of the relation is:

The digraph shows that T = ( R, k ) is a binary tree and of leaves e, d , a, c, f , b, l  . It is seen

that, for example, h is the left child of k and m is the right child, j and c are the left and
right children of h respectively.

We can obtain many subtrees of T = ( R, k ) , for example:

T (h) T ( j) T (g)

52
Faculty of IT & CS == Discrete Mathematics - Relations == Spring 2020 - Prof. Reda S Tantawi

3. Let R be a relation on the set A = a, b, c, d , e, f , g , h, i, j , k , l , m such that:

R = (k , b),(k , l ),( h, m),( h, j ), (i, d ),(i, e),( j, a),( j, i),( g , h),( g , c), (c , f ),(c, k )

The graph of the relation is

The digraph shows that R is a binary tree of root g and leaves e, d , a, m, f , b, l . It is seen

that, for example, h is the left child of g and c is the right child, e and d are the left and
right children of i respectively.

We can obtain many subtrees of T = ( R, k ) , for example:

T (h) T (c )

53
Faculty of IT & CS == Discrete Mathematics - Relations == Spring 2020 - Prof. Reda S Tantawi

Exercises:
1. Determine whether the relation R on the set A = a, b, c, d , e, f , g , h, i, j , k  such that:

R = (b, g ),(b, i ),(d , e),(d , f ),(e, c),(e, b),( f , j ),( f , k ),( k , a),( k , h) ,

is a tree or not, if yes, find its root and leaves.

2. Determine whether R on the set A = a, b, c, d , e, f , g , h, i, j , k , l , m, n, o such that:

R = (c, a),(c, g ),( f , c),( f , i),( g , m),( g , n),( h, l ),( h, k ),(i, b),(i, h), (k , j ),(k , e),(n, d ),(n, o) ,
is a tree or not, if yes, find its root and leaves.

3. Determine whether R on the set A = a, b, c, d , e, f , g , h, i, j , k  such that:

R = (a, d ),(a, g ),(d , e),(d , h),( f , i ),( f , j ),( g , c),( g , k ),( k , b),( k , f ) ,
is a tree or not, if yes, find its root and leaves.

4. Verify that which of the relations R1 and R2 on the set A= 1,2,3,4,5,6 such that:

R1 = (2,1),(3,4),(5,2),(6,5),(6,3) ,

R2 = (1,2),(1,3),(4,5),(4,6) ,
is a tree and find its root and leaves.

54
Faculty of IT & CS == Discrete Mathematics - Relations == Spring 2020 - Prof. Reda S Tantawi

Expression Tree of mathematical expressions

Expression tree of mathematical expression is a binary tree in which each internal node

corresponds to operator (such as +, −, , ) and each leaf node (the leaves) corresponds to
operand, such as constants (numbers) or variable names (such as x, y, ). These particular
trees happen to be binary, because all of the operations are binary. It is also possible for a
node to have only one child, as is the case with the unary minus operator.
An expression tree can be evaluated by applying the operator at the root to the values
obtained by recursively evaluating the left and right subtrees. It is worth to mention that each
parenthes form a subtree.
For examples

1. The expression tree for 3x + (5 − y ) 2 can be obtained by considering that the operator +

between 3x and (5 − y ) 2 represents the root of the tree of the given expression. So that we

should form the left subtree for 3x and the right subtree for (5 − y ) 2 . Then the required
expression tree would be:

The left subtree The right subtree The expression tree

2. The expression tree for (5a − 3b)2 (3a + 2b)3 can be obtained by considering that the

product operator  between the expressions (5a − 3b) 2 and (3a + 2b)3 represents the root of

the tree of the given expression. So that we should form the left subtree for (5a − 3b) 2 and the

right subtree for (3a + 5b)3 . Then the required expression tree would be:

55
Faculty of IT & CS == Discrete Mathematics - Relations == Spring 2020 - Prof. Reda S Tantawi

The left subtree The right subtree

The expression tree

Exercises:
Construct the expression tree of each of the following mathematical expression:
1. (7 + (6 − z )) − ( x − 3 y )
2. ((2 x + 3)  y )  (6 − x)

3. (a − b)2 − (3a + b)
4. ((2a − 3b) + 5) − (1− 3a)
5. ((2 + x) − 3 y) − ( x + y)
6. 3 − ( x + 6(4  y ))

56
Faculty of IT & CS == Discrete Mathematics - Relations == Spring 2020 - Prof. Reda S Tantawi

Binary Tree Traversal ‫التجول ضمن شجرة ثنائية‬

In a traversal of a binary tree, each element of the binary tree is visited exactly once. The
postorder method ‫ طريقة الترتيب الالحق‬is one of the binary tree traversal methods.
Postorder of a binary tree of two edges allows visiting the left child first then the right child
and we visit to root finally (we write the left child then the right one and finally we write the
root of the tree). For a binary tree containing subtrees, we start from the left subtree, then we
go to the right subtree.
Postorder of an expression tree converts it to a postfix notation (expression) )‫الترميز (التعبير‬
‫الالحق‬. In the postfix notation, the binary operator follows the quantities on which it acts. The
postfix notation helps us to calculate the value of the mathematical expression of the
expression tree correctly. A great advantage of this notation is that they eliminate the need for
parentheses in writing arithmetic expressions.

For examples
1. The postfix expression of the expression tree

is A 2  2 A* B * − B 2  + A B − /

57
Faculty of IT & CS == Discrete Mathematics - Relations == Spring 2020 - Prof. Reda S Tantawi

2. The postfix expression of the expression tree

is 3 x *5 y − 2  +

3. The postfix expression of the expression tree

is ab + c d − *e f + /

Remark
We can use comma ‘ , ‘ between the nodes if we have numbers greater than 9.

58
Faculty of IT & CS == Discrete Mathematics - Relations == Spring 2020 - Prof. Reda S Tantawi

Exercises:
Convert each of the following binary expression tree to the associated postfix expression:

T1 T2

T3 T4

T5 T6
59
Faculty of IT & CS == Discrete Mathematics - Relations == Spring 2020 - Prof. Reda S Tantawi

The value of a postfix expression

In postfix notation, the posfix expression 8 4 + 6 / is evaluated from left to right as
follows: Add 8 and 4 to obtain 12, and then divide 12 by 6 to obtain 2.
Another example, the posfix expression 2 6 * 8 2 / + is evaluated from left to right as
follows: Multiply 2 by 6 to obtain 12, divide 8 by 2 to obtain 4, and add 12 and 4 to obtain 16.

More examples
1. The value of the posfix expression 5, 12, 3, /, * is given as: Divide 12 by 3 to obtain 4,
multiply 5 by 4 to obtain 20.
5, 12, 3, /, *
5, 12 / 3, *
5, 4, *
5* 4 = 20

2. The value of the posfix expression 4 9 3 / + 7 3 1 − * + is given as: Divide 9 by 3 to

obtain 3, add 4 and 3 to obtain 7, subtract 1 from 3 to obtain 2, multiply 7 by 2 to obtain
14, and add 7 and 14 to obtain 21.
4 9 3 / + 7 31 − * +
4 9/3 + 7 31 − * +
4 3 + 7 31 − * +
4+3 7 3 1 − * +
7 7 31 − * +
7 7 3 −1 * +
772 * +
7 7*2 +
7 14 +
7 +14 = 21

Note that the operands in order 7 3 1 without operands means that we started with the right
subtree of the expression.

60
Faculty of IT & CS == Discrete Mathematics - Relations == Spring 2020 - Prof. Reda S Tantawi

3. The value of the posfix expression 4 5 7 2 + − * is given as: Add 7 and 2 to obtain 9,
subtract 9 from 5 to obtain -4, multiply 4 by -4 to obtain -16.

4572 + − *
4 5 7+2 − *
459 − *
4 5−9 *
4 −4 *
4 * (−4) −16

Exercises:
Evaluate the following postfix expressions:
1. 4 9 3 / * 7 31 − * −
2. 14, 70, 10, /, *, 4 −
3. 2 2 4 2 / − * 6 1 / +

4. 723 * − 4 * 93 /+

5. 2 3 4 / 23 * 5 − +

61