BIGtheme.net http://bigtheme.net/ecommerce/opencart OpenCart Templates
Saturday , July 22 2017

# Relation

## Relation

Binary relation: A binary relation from A to B is a subset of A×B. A binary relation is indeed only a formalization of the initiative notion that some of the elements in A related to the some of the elements in B. If R is a binary relation from A to B and if the ordered pair (a,b) is in R then we would say that the element a is related element b.

Example: A = {a, b, c}

B = {α, β, γ}

R= {(a, α), (b, β), (c, γ)}

Properties of binary relation:

1) Reflexive: Let R be a binary relation on A. R is said to reflexive if (a, a) is in R for every a in A.

Example: Let A be a set of positive integers and let us define a binary relation R on A such that (a, b) in R if and only if a divides b. Since an integer always divides itself. So R is a reflexive relation.

2) Symmetric relation: Let R be a binary relation on A. R is said to be symmetric relation if (a, b) in R implies that (b, a) is also in R.

Example: i) A = {a, b, c}

And R = {(a, a), (a, b), (b, a), (a, c), (c, a)}

ii) Let A be set of all students in class X. T be binary relation on A such that (a, b) is in T if and only if (a ,b) are students of group science.

3) Anti-symmetric relation: Let R be a binary relation on A, R is said to be anti symmetric if (a, b) is in R implies that (b, a) in R unless a=b.

Example: i) Let be set of tests to be performed on a patient in the hospital and let R be binary relation on A such that if (a, b) is in R, then test a must be performed before test b, then test b must not be performed before test a for two distinct a and b. Thus A, R is an anti –symmetric relation.

ii) Let A be asset of positive integers and R be a binary relation on A such that (a ,b) is in R if and only if a ≥ b.

4) Transitive relation: Let R be a binary relation on A. R is said to be transitive if     (a, c) is in R whenever both (a, b) and (b, c) in R.

Example: Let A be a set of positive integer. R is a binary relation, (a, b) is in R such that a < b.

A = {2, 3, 4}

R = {(2, 3), (2, 4), (3, 4)}

5) Transitive extension: Let R be a binary relation on A. The transitive extension of R denoted R1, is a binary relation on A such that R1 contains R, moreover if (a, b) and (b, c) are in R then (a, c) is in R1.

Example: A = {a, b, c, d}

R = {(a, b), (b, c), (c, b), (c, d)}

R1={(a, b), (a, c), (b, b), (b, c), (b, d), (c, b), (c, c), (c, d)}.

6) Equivalence relation: A binary relation on a set A is said to be a equivalence relation if it is reflexive, symmetric, and transitive.

Example: Let A = {a, b, c, d}

and R = {(a, a), (a, b), (b, c), (c, b), (a, c),(b, a),(b, b), (c, c), (c, d), (d, d)}

7) Partition: Let A be asset. The partition of A is a set of non-empty subsets of a denoted {A1, A2, ……., An} such that the union of Ai ‘s is equal to P and intersection of Ai ‘s and Aj ‘s is empty for any distinct Ai and Aj.

Example: Let A= {a, b, c, d, e, f} then {{a}, {b, c, d}, {c, f}} is a partition of A.

8) Partially ordering relation: A binary relation on a set A is said to be a partially ordering relation if it is reflexive, anti-symmetric, and transitive.

Example: Let A be set of positive integers and R be binary relation on A such that (a, b) in R if a divided by b

A = {1, 2, 3}

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

9) Partially ordered set: A set A together with a partially ordering relation R on A is called partially ordered set.

## Procedure for computing shortest distance| Discrete Mathematics

Solution: The procedure for computing the shortest distance/path from a to any vertex G. Initially, ...