transitive closure


Also found in: Acronyms, Wikipedia.

transitive closure

The transitive closure R* of a relation R is defined by

x R y => x R* y x R y and y R* z => x R* z

I.e. elements are related by R* if they are related by R directly or through some sequence of intermediate related elements.

E.g. in graph theory, if R is the relation on nodes "has an edge leading to" then the transitive closure of R is the relation "has a path of zero or more edges to". See also Reflexive transitive closure.
References in periodicals archive ?
4, the structure of the inverse of a matrix F is given by the transitive closure of the directed graph of the transposed matrix [F.
The transitive closure of the directed graph of such a basis leads to few 'fill edges' for the many vertices in the first set, and to greater 'fill' for the few vertices in the second set.
4 that the directed graph of the inverse of a matrix is the transitive closure of the directed graph corresponding to the matrix.
This is no more than a shorthand for saying that the tuple belongs to the reflexive transitive closure of the generator set.
The expansion of a generator set by two sets whose reflexive transitive closure is equal yields generator sets whose closure is also equal.
As long as there is a path in the generator set from i to j, (i,j) will be found in its transitive closure.
We may also define the left (weak) Bruhat order on W to be the transitive closure of the relations w [<.
l} is defined to be the transitive closure of the relations j > j' for all j < j' in integers such that [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] do not commute.
These results concern combinatorial properties of the increasing flip poset [GAMMA](Q, [rho]), defined as the transitive closure of the increasing flip graph G(Q, [rho]).
In this paper, we consider edge labelings of finite, acyclic, directed graphs which might differ from the Hasse diagrams of their transitive closures.