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 [g] in the Wolfram Language package .

See also

Reflexive Closure, Transitive Reduction

Explore with Wolfram|Alpha

References

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 Resource. https://mathworld.wolfram.com/TransitiveClosure.html

Subject classifications