• :00Days
• :00Hours
• :00Mins
• 00Seconds
A new era for learning is coming soon

Suggested languages for you:

Americas

Europe

Q58E

Expert-verified
Found in: Page 583

### Discrete Mathematics and its Applications

Book edition 7th
Author(s) Kenneth H. Rosen
Pages 808 pages
ISBN 9780073383095

# (a) To find Relation$${R^2}$$(b) To find Relation $${R^3}$$(c) To find Relation $${R^4}$$(d) To find Relation$${R^5}$$

(a)The solution of Relation$${R^2} = \left\{ \begin{array}{l}(1,1),(1,2),(1,3),(1,4),(1,5),\\(2,1),(2,2),(2,4)(2,5),\\(3,1),(3,2),(3,3),(3,4),(3,5),\\(4,1),(4,2)(4,3),(4,4),\\(5,1),(5,2),(5,3),(5,4),(5,5)\end{array} \right\}$$

(b) The solution of Relation$${R^3} = \left\{ \begin{array}{l}(1,1),(1,2),(1,3),(1,4),(1,5),\\(2,1),(2,2),(2,3),(2,4),(2,5),\\(3,1),(3,2),(3,3),(3,4),(3,5),\\(4,1),(4,2),(4,3),(4,4),(4,5),\\(5,1),(5,2),(5,3),(5,4),(5,5)\end{array} \right\}$$

(c) The solution of Relation $${R^4} = \left\{ \begin{array}{l}(1,1),(1,2),(1,3),(1,4),(1,5),\\(2,1),(2,2),(2,3),(2,4)(2,5),\\(3,1),(3,2),(3,3),(3,4),(3,5),\\(4,1),(4,2)(4,3),(4,4),(4,5),\\(5,1),(5,2),(5,3),(5,4),(5,5)\end{array} \right\}$$

(d) The solution of Relation$${R^4} = \left\{ \begin{array}{l}(1,1),(1,2),(1,3),(1,4),(1,5),\\(2,1),(2,2),(2,3),(2,4)(2,5),\\(3,1),(3,2),(3,3),(3,4),(3,5),\\(4,1),(4,2)(4,3),(4,4),(4,5),\\(5,1),(5,2),(5,3),(5,4),(5,5)\end{array} \right\}$$

See the step by step solution

## Step 1:  Given

(a) Relation $$R = \{ (1,1),(1,2),(1,3),(2,3),(2,4),(3,1),(3,4),(3,5),(4,2),(4,5),(5,1)$$,

$$\qquad (5,2),(5,4)\}$$

On set $$A = \{ 1,2,3,4,5\}$$

(b) Relation$$R = \{ (1,1),(1,2),(1,3),(2,3),(2,4),(3,1),(3,4),(3,5),(4,2),(4,5),(5,1)$$$$\qquad (5,2),(5,4)\}$$

On set $$A = \{ 1,2,3,4,5\}$$.

(c) Relation$$R = \{ (1,1),(1,2),(1,3),(2,3),(2,4),(3,1),(3,4),(3,5),(4,2),(4,5),(5,1)$$$$\qquad (5,2),(5,4)\}$$

On set $$A = \{ 1,2,3,4,5\}$$.

(d) Relation$$R = \{ (1,1),(1,2),(1,3),(2,3),(2,4),(3,1),(3,4),(3,5),(4,2),(4,5),(5,1)$$$$\qquad (5,2),(5,4)\}$$

On set $$A = \{ 1,2,3,4,5\}$$.

## Step 2: The Concept ofrelation

An n-array relation on n sets, is any subset of Cartesian product of the n sets (i.e., a collection of n-tuples), with the most common one being a binary relation, a collection of order pairs from two sets containing an object from each set. The relation is homogeneous when it is formed with one set.

## Step 3: Determine the value of relation (a)

Consider the relation $$R$$

$${R^2} \Rightarrow$$ paths of length 2

$$\begin{array}{c}{R^2} = R \cdot R\\ = \{ (1,1),(1,2),(1,3),(1,4),(1,5),\\(2,1),(2,2),(2,4),(2,5),\\(3,1),(3,2),(3,3),(3,4),(3,5),\\(4,1),(4,2),(4,3),(4,4),\\(5,1),(5,2),(5,3),(5,4),(5,5)\} \end{array}$$

## Step 4: Determine the value of relation (b)

Consider the relation $$R$$

$${R^3} \Rightarrow$$ paths of length 3

$$\begin{array}{c}{R^3} = {R^2}.R\\ = \{ (1,1),(1,2),(1,3),(1,4),(1,5),\\(2,1),(2,2),(2,3),(2,4)(2,5),\\(3,1),(3,2),(3,3),(3,4),(3,5),\\(4,1),(4,2)(4,3),(4,4),(4,5),\\(5,1),(5,2),(5,3),(5,4),(5,5)\} \end{array}$$

## Step 5: Determine the value of relation (c)

Consider the relation $$R$$

$${R^4} \Rightarrow$$ paths of length 4

$$\begin{array}{c}{R^4} = {R^3} \cdot R\\ = \{ (1,1),(1,2),(1,3),(1,4),(1,5),\\(2,1),(2,2),(2,3),(2,4)(2,5),\\(3,1),(3,2),(3,3),(3,4),(3,5),\\(4,1),(4,2)(4,3),(4,4),(4,5),\\(5,1),(5,2),(5,3),(5,4),(5,5)\} \end{array}$$

## Step 6: Determine the value of relation (d)

Consider the relation $$R$$

$${R^5} \Rightarrow$$ paths of length 5

$$\begin{array}{c}{R^5} = {R^4} \bullet R\\ = \{ (1,1),(1,2),(1,3),(1,4),(1,5),\\(2,1),(2,2),(2,3),(2,4),(2,5),\\(3,1),(3,2),(3,3),(3,4),(3,5),\\(4,1),(4,2),(4,3),(4,4),(4,5),\\(5,1),(5,2),(5,3),(5,4),(5,5)\} \end{array}$$