Find the transitive closure of {$(1,2),(2,3),(4,4),(5,4),(5,7)$}

Question

I want to find the transitive closure of $R=${$(1,2),(2,3),(4,4),(5,4),(5,7)$}. I'm having trouble with transitive closure. We have that $(1,2)$ and $(2,3)$, so the transitive closure of $R$ is $R ∪ $ {$(1,3)$}. Is this right?

Thanks.

Answer 1

The composition of two relations $A,B$ is the relation $A \circ B = \{ (x,z) | \exists y \text{ such that } (x,y) \in A \text{ and } (y,z) \in B\} $.

The transitive closure of $R$ is smallest transitive relation that contains $R$.

It can be computed explicitly as follows: Let $R_0 = R$, $R_{n+1} = R_n \cup (R \circ R_n)$, $R^+ = \cup_n R_n$.

Clearly if $R_k = R_{k+1}$ for some $k$, we have $R^+ = R_k$.

In the example in the question, we have $R_2 = R_3$, hence $R^+ = R \cup (R \circ R)$, which is what you have above.

Answer 2

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