# Types of Relation | Discrete Mathematics

In this article, we will learn about the **relations and the different types of relation in the discrete mathematics**.

Submitted by Prerana Jain, on August 17, 2018

## Types of Relation

There are many types of relation which is exist between the sets,

**1. Universal Relation**

A relation r from set a to B is said to be universal if: **R = A * B**

**Example:**

**A = {1,2} B = {a, b}**

**R = { (1, a), (1, b), (2, a), (2, b) is a universal relation.**

**2. Compliment Relation**

Compliment of a relation will contain all the pairs where pair do not belong to relation but belongs to Cartesian product.

**R = A * B – X**

**Example:**

A = { 1, 2} B = { 3, 4} R = { (1, 3) (2, 4) } Then the complement of R Rc = { (1, 4) (2, 3) }

**3. Empty Relation**

A null set phie is subset of **A * B**.

**R = phie is empty relation**

**4. Inverse of relation**

An inverse of a relation is denoted by **R^-1** which is the same set of pairs just written in different or reverse order. Let **R** be any relation from **A to B**. The inverse of **R** denoted by **R^-1** is the relation from **B to A** defined by:

R^-1 = { (y, x) : yEB, xEA, (x, y) E R}

**5. Composite Relation**

Let **A**, **B**, and **C** be any three sets. Let consider a relation **R** from **A to B** and another relation from **B to C**. The composition relation of the two relation **R** and **S** be a Relation from the **set A** to the **set C**, and is denoted by **RoS** and is defined as follows:

**Ros = { (a, c) : an element of B such that (a, b) E R and (b, c) E s, when a E A , c E C}Hence, (a, b) E R (b, c) E S => (a, c) E RoS**.

**6. Equivalence Relation**

The relation **R** is called equivalence relation when it satisfies three properties if it is reflexive, symmetric, and transitive in a **set x**. If **R** is an equivalence relation in a **set X** then **D(R)** the domain of **R** is **X** itself. Therefore, **R** will be called a relation on **X**.

The following are some examples of the equivalence relation:

- Equality of numbers on a set of real numbers.
- Equality of subsets of a universal set.
- Similarities of triangles on the set of triangles.
- Relation of lines being a parallel onset of lines in a plane.
- Relation of living in the same town on the set of persons living in Canada.

**7. Partial order relation**

Let, **R** be a relation in a **set A** then, **R** is called partial order Relation if,

**R**is reflexive

i.e. aRa ,a belongs to A**R**is anti- symmetric

i.e. aRb, bRa => a = b, a, b belongs to a**R**is transitive

aRb, bRc => aRc, a, b, c belongs to A

**8. Antisymmetric Relation**

A relation **R** on a set a is called on antisymmetric relation if for **x, y** if for **x, y** =>

**If (x, y) and (y, x) E R then x = y**

**Example: { (1, 2) (2, 3), (2, 2) } is antisymmetric relation.**

A relation that is antisymmetric is not the same as not symmetric. A relation can be antisymmetric and symmetric at the same time.

**9. Irreflective relation**

A relation **R** is said to be on irreflective relation if **x E a (x ,x)** does not belong to **R**.

**Example:**

a = {1, 2, 3} R = { (1, 2), (1, 3) if is an irreflexive relation

**10. Not Reflective relation**

A relation **R** is said to be not reflective if neither **R** is reflexive nor irreflexive.

TOP Interview Coding Problems/Challenges

- Run-length encoding (find/print frequency of letters in a string)
- Sort an array of 0's, 1's and 2's in linear time complexity
- Checking Anagrams (check whether two string is anagrams or not)
- Relative sorting algorithm
- Finding subarray with given sum
- Find the level in a binary tree with given sum K
- Check whether a Binary Tree is BST (Binary Search Tree) or not
- 1[0]1 Pattern Count
- Capitalize first and last letter of each word in a line
- Print vertical sum of a binary tree
- Print Boundary Sum of a Binary Tree
- Reverse a single linked list
- Greedy Strategy to solve major algorithm problems
- Job sequencing problem
- Root to leaf Path Sum
- Exit Point in a Matrix
- Find length of loop in a linked list
- Toppers of Class
- Print All Nodes that don't have Sibling
- Transform to Sum Tree
- Shortest Source to Destination Path

Comments and Discussions