Transitive Closure

The transitive closure of a binary relation R on a set X is the minimal transitive relation R^' on X that contains R. Thus aR^'b for any elements a and b of X provided that there exist c_0, c_1, ..., c_n with c_0=a, c_n=b, and c_rRc_(r+1) for all 0<=r<n.

The transitive closure C(G) of a graph is a graph which contains an edge {u,v} whenever there is a directed path from u to v (Skiena 1990, p. 203). The transitive closure of a graph can be computed using TransitiveClosure[g] in the Wolfram Language package Combinatorica` .

See also

Reflexive Closure, Transitive Reduction

Explore with Wolfram|Alpha


Aho, A.; Garey, M. R.; and Ullman, J. D. "The Transitive Reduction of a Directed Graph." SIAM J. Comput. 1, 131-137, 1972.Skiena, S. Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Reading, MA: Addison-Wesley, 1990.

Referenced on Wolfram|Alpha

Transitive Closure

Cite this as:

Weisstein, Eric W. "Transitive Closure." From MathWorld--A Wolfram Web Resource.

Subject classifications