18.7.3. Transitive Closure

Try these first

1. 1.

   What is the transitive closure of the relation R = {(1, 2), (2, 3)}?

   Hint

   Think of the pairs that need to be added to ensure transitivity.

2. 2.

   Which property must be satisfied for a relation to be a transitive closure?

   Hint

   If A is related to B and B is related to C, what must also be true?

3. 3.

   What is the transitive closure of a relation?

   • A set containing direct pairs
   • The smallest superset satisfying transitive properties
   • A completely arbitrary set

   Hint

   Remember the goal is to ensure A relates to C if A relates to B and B to C.

4. 4.

   True or False: The transitive closure can be computed in a single step.

   • True
   • False

   Hint

   Think back to our example!

5. 5.

   You have a relation R = {(1, 2), (2, 3), (4, 5)}. Find R's transitive closure and explain the steps taken.

   Hint

   Look at pairs and see if they indirectly relate to each other.

6. 6.

   Given the relation R = {(a, b), (b, c), (c, d), (d, a)}, calculate its transitive closure.

   Hint

   Consider how far each node can reach through others.