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

R2={(a,c),(b,a),(c,b)}

R3={(a,a),(b,b),(c,c)}

R4={(a,b),(b,c),(c,a)}

so for 1st digraph m=1 and n=4 R1=R4 this what you want to say.?

The Gateway to Computer Science Excellence

+4 votes

Let $R$ be a binary relation on $A = \{a, b, c, d, e, f, g, h\}$ represented by the following two component digraph. Find the smallest integers $m$ and $n$ such that $m < n$ and $R^m = R^n$.

+7 votes

Best answer

For every non-empty set $A$, if $R$ is a binary relation on $A$ then-

$R^0$ is an identity relation on A which is defined as - $R^0= \{(x,x) \mid x \in A \}$

Also, if a relation has a cycle of length $n$ then its $n^{th}$ power is reflexive an identity relation. So for first component, $R_3$ is reflexive and hence $R_0=R_3.$

Similarly, for second component $R_0=R_5.$ LCM of $3$ and $5$ is $15.$

So $m=1$ and $n=12.$

$\text{LCM}$ of $3$ and $5$ is $15.$ So, $m = 0 \ and \ n=15.$

Check this for having some intuition behind $R^0$.

PS: Here, $R_1 = R4; R_2 = R_6$ and we get $m=1, n=12.$ But question asks for smallest $m,n.$

0

+Saumya29

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

R2={(a,c),(b,a),(c,b)}

R3={(a,a),(b,b),(c,c)}

R4={(a,b),(b,c),(c,a)}

so for 1st digraph m=1 and n=4 R1=R4 this what you want to say.?

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

R2={(a,c),(b,a),(c,b)}

R3={(a,a),(b,b),(c,c)}

R4={(a,b),(b,c),(c,a)}

so for 1st digraph m=1 and n=4 R1=R4 this what you want to say.?

+1

**Part (B)**

For clear understanding and solution for part (B) just watch Kamala krithivasan mam video lectures on Relations.

+1

I didn't understand this part " LCM of 3 and 5 is 15. So, *m*=0 *a**n**d* *n*=15"

can someone please explain , how to get m and n

+1

@Sherrinford This should help you.

@Soumya29 You need to edit your answer as $R_2 $ not equal to $R_6$ but $R_1 $ equal to $R_6$

+19 votes

First component repeats after every 3^{rd} power of R,

R^{0} -> R^{1} -> R^{2} -> R^{0}

R^{0} = R^{3} = R^{6} = ........

Second component repeats after every 5th power of R,

R^{0} -> R^{1} -> R^{2} -> R^{3} -> R^{4} -> R^{0}

R^{0} = R^{5} = R^{10} = ........

The relation R is the combination of two components.

So R will repeat after every LCM(3,5) = 15^{th} power of R.

Thus R^{0} = R^{15} = R^{30} = ........

So, m = 0 & n = 15.

For more information, watch this lecture:

52,375 questions

60,553 answers

201,952 comments

95,374 users