GATE CSE 1989 | Question: 1-iv

Question

The transitive closure of the relation $\left\{(1, 2), (2, 3), (3, 4), (5, 4)\right\}$ on the set $\left\{1, 2, 3, 4, 5\right\}$ is ___________.

Answer 1

Transitive closure of $R$

1. It is transitive.
2. It contains $R.$
3. It is minimal satisfies $1$ and $2.$

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

The transitive closure of the relation R = {(1,2),(2,3),(1,3) ,(3,4),(2,4),(1,4),(5,4)}

Comments

Is this an standard defination, i didnt find it anywhere can you provide me some reference to it.

---

is (1,4) necessary?

aRb and bRc implies aRc

so (1,2) , (2,3) => (1,3)

(2,3), (3,4) =>(2,4)

 

why (1,4)?

---

$(1, 2), (2, 4) => (1, 4)$

---

(1,3),(3,4) → (1,4)

(1,2),(2,4) → (1,4)

Answer 2

Ans: {(1,2),(2,3),(1,3) ,(3,4),(2,4),(1,4),(5,4)}

Comments

Best Solution

---

@mohan123 Thanks bro.

---

This is the best way to answer such questions

Answer 3

draw a directed graph

Transitive closure can be found using the graph.Include all the pair of vertices for which the path exist in the graph

Comments

perfect!

---

Good aproach

Answer 4

The transitive closure of the relation $\left \{ (1,2),(2,3),(3,4),(5,4)\right \}$ =$\left \{ (1,2),(2,3),(1,3) ,(3,4),(2,4),(1,4),(5,4)\right \}$