How to find Transitive Closure of any Relation ?

Question

I want to know the best way through which we can find transitive closures of any relation ? Please let me know.

Answer 1

If r is a relation on a then it's xsitive closure = the smallest xsitive relation on a which contain r ...eg a={a,b,c} and r= {(a,c),(c,b)} then r* = { (a,c),(c,b),(a,b)}

Comments

Are there any better way to find it in quick time rather than checking each pairs again n again ? Just for e.g. R= {(1,3),(1,4),(2,1),(3,2)} on the set {1,2,3,4} .. it's not transitive ! so we add (1,2), (2,3), (2,4) and (3,1) .. but again it's not transitive as (3,4) is not there which came 'coz of added ordered pair (3,1) & (1,4) from original.So we continue checking each pair again and again which takes a lot of time and you might end up missing a pair.

Answer 2

You can check Relations chapter in Keneth Rosen, Relations chapter, where you can find Closures topic. There is method for finding transitive closure using Matrix Multiplication.