i get trouble in one problem...

if we have relation R={(a,b), (b,c), (b,d), (c,e), (d,e), (c,f), (e,a)}, on set {a,b,c,d,e,f}. how many elements the transitive closure of R has?

I try google it, but I couldn't find any relation. anyone can help me ?

I know about relation, but this is a hard problem. everyone could help me ?

  • $\begingroup$ Dear @MauroALLEGRANZA, i know it but i couldn't find the answers... $\endgroup$ – Maryam Ghizh Feb 8 '15 at 13:40
  • $\begingroup$ no, i not prefer this way... $\endgroup$ – Maryam Ghizh Feb 8 '15 at 13:42
  • $\begingroup$ Dear @MauroALLEGRANZA, there is 30 ? would you please wrote it some of them and the total elements ? $\endgroup$ – Maryam Ghizh Feb 8 '15 at 13:44

Recall that a relation is transitive if for all $a, b, c$ in $\{a, b, c, d, e, f\}$, if $(a, b)\in R$ and $(b, c) \in R$, then $(a, c) \in R$. Your job is to extend $R$ so that it is transitive.

You need to find, and add to the given set, all pairs $(x, z)$ for which $(x, y)\in R$ and $(y, z) \in R)$, if $(x, z)$ is not already in the set.

E.g., $(a, b) \in R$ and $(b, c) \in R$, so we need to add $(a,c)$, because it is not already in $R$. Call the new set, including all of $R$ plus any needed pairs for transitive closure, $R_t$.

Be careful to check if any newly added pairs to $R_t$ require additional pairs to be added. For example, in $R$, we have $(c, e)$ and $(e, a)$, so we have to add $(c, a)$. Once that is added, since $(b, c)$ is in the original $R$, and we added $(c, a)$, we also need then to add $(b, a)$ to the emerging set $R_t$.

  • $\begingroup$ dear amwhy, would you please add the total count ? $\endgroup$ – Maryam Ghizh Feb 8 '15 at 13:46
  • 1
    $\begingroup$ You need to do some work here. I've given you the tools you need. Examine the set, write down the original pairs in $R$, add those pairs needed for transitive closure, until you've obtained such closure, then count them. It's just as important you know how to achieve transitive closure as it is to know the number of pairs in such closure. I'm addressing the "how" so you can obtain the answer. $\endgroup$ – amWhy Feb 8 '15 at 13:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.