Transitive Closure

Transitive Closure of a Directed Graphs G is the digraph G with the same vertices as G, where G has a directed edge from u to v whenever G has a directed path from u to v.

In other words, it adds a direct edge for everything that's reachable, so it's a handy way to capture reachability information about a graph. To construct it, you keep adding any missing edge (u, w) where edges (u, v) and (v, w) already exist, until nothing changes.

The same idea applies to a Relation: the transitive closure of a relation is the smallest transitive relation that contains it.

See Week 13 - Graphs A and Week 14 - Graphs B.