RELATIONS - Discrete Structures

RELATIONS

INTRODUCTION

A relation can be thought of as a structure (for example, a table) that represents the relationship of elements of a set to the elements of another set.

Example

  1. Employees and their salaries
  2. Name of the students and their roll numbers
  3. Industries and their telephone numbers

BINARY RELATIONS

To express a relationship between elements of two sets is to use ordered pairs consisting of two related elements. Due to this reason, sets of ordered pairs are called binary relations.

Definition

When A and B are sets, a subset R of the Cartesian product AxB is called a binary relation from A to B.

If R is a binary relation from A to B, R is a set of ordered pairs (a, b), where a ∈ A and b ∈ B. When (a, b) ∈ R, we use the notation a R b and read it as “a is related to b by R”. If (a, b) ∉ R, it is denoted as "a is not related to b by R".

Domain and Range of Relation

If there are two sets A and B, and relation R have order pair (a, b) then

The set {a ∈ A | (a, b) ∈ R, for some b ∈ B} is called the domain of R and denoted by Dom (R)

The set {b ∈ B | (a, b) ∈ R, for some a ∈ A} is called the range of R and denoted by Ran (R)

Example

Let A = {1,2,3,4 and B = {2,3,4,5 and (a, b) ∈ R if and only if a + b = 6 then

R = {(1,5), (2,4), (3,3), (4,2)

The domain of R = {1,2,3,4

The range of R = {2,3,4,5

 

Relation on a set

If R is a relation from a set A to itself, if R is a subset of AxA, then R is called a relation on the set A.

Example

Let R be the relation on A = {1,2,3,4,

defined by (a, b) ∈ R if a≤b, a and b ∈ A,

then R = {(1,1), (1,2), (1,3), (1,4), (2,2), (2,3), (2,4), (3,3 ), (3,4), (4,4)

The domain and range of R are both equal to A

 

TYPES OF RELATIONS

Void Relation

A relation R on a set A is called Void Relation if R is the null set.

Example

If A = {1,2,3} and R is defined as (a, b) ∈ R if and only if a + b> 10,

then R is a null set, since no element in AxA satisfies the given condition.

Note: AxA = {(1,1), (1,2), (1,3), (2,1), (2,2), (2,3), (3,1), (3, 2), (3,3)

Universal Relation

A relation R on a set A is called universal relation, if R = AxA.

Example

If A = {1,2,3, then R = AxA = {(1,1), (1,2), (1,3), (2,1), (2,2), (2, 3), (3,1), (3,2), (3,3)} is the universal relation on A.

Identity Relation

A relation R on a set A is called an identity relation, if R = {(a, a) | a ∈ A} and it is denoted by I A.

Example

If A = {1,2,3, then R = {(1,1), (2,2), (3,3) is the identity relation on A.

Inverse of Relation

When R is any relation from a set A to a set B, the inverse of R, denoted by R -1 , is the relation from B to A which consists of those ordered pairs got by interchanging the elements of the ordered pairs in R.

R -1 = {(b, a) | (a, b) ∈ R

Example

If A = {1,2,3, then R = {(1,2), (2,3), (3,1)

                   Now R -1 = {(2,1), (3,2), (1,3)


MATRIX REPRESENTATION OF A RELATION

If R is a relation from the set A = {a 1 , a 2 , …… .a n } to the set B = (b 1 , b 2 , ……… b n }, where the element of A and B are assumed to be in a specific order, the relation R can be represented by the matrix

The matrix of the relation = M R = [m ij ], where

 

Example

1. Let A = {1,2,3,4} and B = {2,3,4,5} and (a, b) ∈ R if and only if a + b = 6 then

R = {(1,5), (2,4), (3,3), (4,2)

                2 3 4 5

            1 | 0 0 0 1 |

  M R = 2 | 0 0 1 0 |

            3 | 0 1 0 0 |

            4 | 1 0 0 0 |

 2. Let R be the relation on A = {1,2,3}, defined by (a, b) ∈ R if a≤b, a and b ∈ A,

then R = {(1,1), (1,2), (1,3), (2,2), (2,3), (3,3)

                 1 2 3 

             1 | 1 1 1 |

  M R = 2 | 0 1 1 |

             3 | 0 0 1 |

 

REPRESENTATION OF RELATIONS BY GRAPHS

Let R be relation on a set A. To represent graphically as follows

Draw a small circle, called a vertex / node, for each element of A and label the circle with the corresponding element of A.

Draw an arrow, called an edge / link, from vertex a i to vertex a j iff (a i , a j ) ∈ R.

The resulting diagram is called the directed graph or digraph of R.

The edge of the form (a, a), represented by using an arc from the vertex a back to itself, is called a loop.

Example

1. If R is the relation on a set A = {1,2,3} defined by (a, b) ∈ R if a <b, where a, b ∈ A, then            

R = {(1,2), (1,3), (2,3)

2. Let R be the relation on A = {1,2,3}, defined by (a, b) ∈ R if a≤b, a and b ∈ A,

then R = {(1,1), (1,2), (1,3), (2,2), (2,3), (3,3)



PROPERTIES OF RELATIONS

Reflexive

A relation R on a set A is said to be reflexive, if aRa for every a ∈ A.

Example

If R is the relation on a set A = {1,2,3} defined by (a, b) ∈ R if a≤b, where a, b ∈ A, then R = {(1,1), (1 , 2), (1,3), (2,2), (2,3), (3,3). 

Now R is reflexive, since each of the elements of A is related to itself, as (1,1), (2,2), (3,3) are members of R.

 

Irreflexive

A relation R on a set A is called reflexive, if, for every a ∈ A, (a, a) ∉ R

Example

R = {(1,2), (2,4), (3,6)

 

Symmetric

A relation R on a set A is called symmetric, if (b, a) ∈ R holds when (a, b) ∈ R.

Example

R = {(4,5), (5,4), (6,5), (5,6)} on set A = {4,5,6 is symmetric.

 

Asymmetric or Not symmetric

Asymmetric relation is the opposite of symmetric relation.

A relation R on a set A is called asymmetric if (b, a) ∉ R when (a, b) ∈ R.

Example

R = {(1,2), (2,4), (3,6)

 

Anti-Symmetric

A relation R on a set A is called anti-symmetric

if (a, b) ∈ R and (b, a) ∈ R then a = b.

The relation R = {(a, b) ∈ R | a ≤ b} is anti-symmetric since a ≤ b and b ≤ a implies a = b.

Example

R = {(1,1), (2,2), (3,3) is anti-symmetric

 

Not Anti-Symmetric

A relation R on a set A is called not anti-symmetric

If there exist a, b ∈ A such that (a, b) ∈ R and (b, a) ∈ R then a ≠ b.

Example

R = {(4,5), (5,4)

(4,5) and (5,4) ∈ R but 4 ≠ 5

 

Transitive

A relation R on a set A is called transitive if (a, b) ∈ R and (b, c) ∈ R then (a, c) ∈ R for all a, b, c ∈ A.

Example

R = {(1,2), (2,3), (1,3)} on set A = {1,2,3 is transitive.

 

Not Transitive

A relation R on a set A is called not transitive if (a, b) ∈ R and (b, c) ∈ R then (a, c) ∉ R for all a, b, c ∈ A.

Example

R = {(1,2), (2,3), (1,4)} on set A = {1,2,3,4 is not transitive.

 

Equivalence Relation

A relation R on a set A is said to be an equivalence relation if R is reflexive, symmetric and transitive.

ie, if it has the following three properties

1. (a, a) ∈ R for every a ∈ A

2. if (a, b) ∈ R then (b, a) ∈ R

3. if (a, b) ∈ R and (b, c) ∈ R then (a, c) ∈ R

Example

R = {(1,1), (2,2), (3,3), (1,2), (2,1), (2,3), (3,2), (1,3) , (3,1)} on set A = {1,2,3} is equivalence relation as it is reflexive, symmetric, and transitive.

ie, reflexive: (1,1), (2,2), (3,3)

       symmetric: (1,2), (2,1), (2,3), (3,2), (1,3), (3,1)

       transitive: (1,2), (2,1), (1,1), (2,3), (3,2), (2,2), (1,3), (3,1), (1,1)

 

Partial ordering

A relation R on a set A is said to be partial ordering or partial order relation if R is reflexive, anti-symmetric and transitive.

ie, if it has the following three properties

1. (a, a) ∈ R for every a ∈ A

2. if (a, b) ∈ R and (b, a) ∈ R then a = b

3. if (a, b) ∈ R and (b, c) ∈ R then (a, c) ∈ R

Note: A set A together with a partial order relation R is called partially ordered set or poset

Example

The greater than or equal to (≥) relation is a partial order relation on the set of integers Z, since

1. a≥a for every integer a, ie, ≥ is reflexive

2. a≥b and b≥a then a = b, ie, ≥ is anti-symmetric

3. a≥b and b≥c then a≥c, ie, ≥ is transitive                   

Thus (Z,⁇) is a poset.


Composition and Closures of Relations

https://deepanotes.blogspot.com/2020/08/closures-of-relations.html

 

Relations – Exercise

https://deepanotes.blogspot.com/2020/08/relations-exercise.html

Comments

Post a Comment

Popular posts from this blog

Backtracking - N-Queens Problem, Sum of Subsets, Graph Colouring, Hamiltonian Cycle

Image
UNIT - V : BACKTRACKING General Method – 8-Queens Problem – Sum Of Subsets – Graph Coloring –  Hamiltonian Cycles General Method Backtracking is a problem-solving technique used in algorithms to find solutions by exploring all possible options. In backtracking, a state-space tree is a tree-like structure that represents all possible states (solutions or non-solutions) of a problem. Backtracking algorithms explore this tree using a depth-first search approach, systematically checking each path until a solution is found or all possibilities have been exhausted.  Here’s how it works, step-by-step: Start with a choice : Make a decision and move forward. Check feasibility : If this choice leads to a solution or partial solution, continue. If not, stop exploring this path. Go back and try a different path : If you reach a dead end, go back to the last point where you made a choice. Try a different path from there. Repeat until you find a solution ...
Read more

Divide and Conquer Technique - Binary Search, Quick Sort, Merge Sort

Image
  UNIT II - DIVIDE AND CONQUER TECHNIQUE General Method – Binary Search – Merge Sort – Quick Sort.  GENERAL METHOD The divide and conquer technique is a problem-solving approach that works in three main steps: 1.       Divide : Break down a large problem into smaller, simpler sub-problems. 2.       Conquer : Solve each of the sub-problems individually. This can often be done recursively if the sub-problems are still large. 3.     Combine : Combine the solutions of the sub-problems to get the solution to the original, larger problem. This approach is commonly used in algorithms like binary search, merge sort and quick sort, where breaking down a problem makes it easier and faster to solve.   BINARY SEARCH Binary search is an efficient algorithm for finding a target value within a sorted list. Here’s how it works: Start in the Middle : Look at the middle element of the list. Compare : ...
Read more

GRAPH THEORY

Image
  GRAPH THEORY DEFINITION A graph G = (V, E) consists of a non-empty set V, called the set of vertices (points, nodes) and a set  of ordered or unordered pairs of elements of V, called the edges E set (links), such that there is a mapping from the set E to the set of ordered or unordered pairs of elements of V. Example In the first graph, V = { A , B , C , D } E = {(A,B) , (A,C) , (A,D), (B,C), (B,D) , (C,D)} In the second graph, V = { E, F, G } E = {(F,E) , (E,G) , (G,F)} If an edge e ∈ E is associated with an ordered pair (u,v) or an unordered pair (u,v), where u,v ∈ V, then e is said to connect or join the nodes u and v.  The edge e that connects the nodes u and v is said to be incident on each of the nodes.  The pair of each node that is connected by an edge is called adjacent nodes . Isolated Nodes If any node has no edges connected with any other node then its degree will be zero(0) and it will be called as isolated node. Adjacent Nodes Her...
Read more