Transitive Reduction

The transitive reduction of a binary relation R on a set X is the minimum relation R^' on X with the same transitive closure as R. Thus aR^'b for any elements a and b of X, provided that aRb and there exists no element c of X such that aRc and cRb.

The transitive reduction of a graph G is the smallest graph R(G) such that C(G)=C(R(G)), where C(G) is the transitive closure of G (Skiena 1990, p. 203).

See also

Reflexive Reduction, Transitive Closure

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 Reduction

Cite this as:

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

Subject classifications