Added to Favorites

Related Searches

Definitions

In mathematics, the transitive closure of a binary relation R on a set X is the smallest transitive relation on X that contains R.## Existence and description

For any relation R, the transitive closure of R always exists. To see this, note that the intersection of any family of transitive relations is again transitive. Furthermore, there exists at least one transitive relation containing R, namely the trivial one: X × X. The transitive closure of R is then given by the intersection of all transitive relations containing R.## Demonstration that T is the smallest transitive relation containing R

### Corollary

## Uses

Note that the union of two transitive relations need not be transitive. In order to preserve transitivity, one must take the transitive closure. This occurs, for example, when taking the union of two equivalence relations or two preorders. In order to obtain a new equivalence relation or preorder one must take the transitive closure (reflexivity and symmetry—in the case of equivalence relations—are automatic).### Graph Theory

## Relationship to complexity

## Related concepts

## Algorithms

## References

For example, if X is a set of airports and xRy means "there is a direct flight from airport x to airport y", then the transitive closure of R is the relation "it is possible to fly from x to y in one or more flights." Or, if X is the set of humans (alive or dead) and R is the relation 'parent of', then the transitive closure of R is the relation "x is an ancestor of y".

We can describe the transitive closure of R in more concrete terms as follows. Define a relation T on X by saying xTy iff there exists a finite sequence of elements (x_{i}) such that x = x_{0} and

- x
_{0}Rx_{1}, x_{1}Rx_{2}, …, x_{n−1}Rx_{n}, and x_{n}Ry

- $T\; =\; bigcup\_\{i\; in\; omega\}\; R^i$

Let A be any set of elements.

Supposition: $exists$G_{A} transitive relationship $left\; /\; right\; .$ R_{A}$subseteq$G_{A} $wedge$ T_{A}$notsubseteq$G_{A}. So, $exists$(a,b)$notin$G_{A}$wedge$(a,b)$in$T_{A}. So, that particular (a,b)$notin$R_{A}.

Now, by definition of T, we know that $exists$n$in\; mathbb\{N\}\; left\; /\; right\; .$ (a,b)$in$R^{n}_{A}. Then, $forall$i$in\; mathbb\{N\}$, i$<$n $Rightarrow$ e_{i}$in$A. So, there is a path from a to b like this: aR_{A}e_{1}R_{A}...R_{A}e_{(n-1)}R_{A}b.

But, by transitivity of G_{A} on R_{A}, $forall$i$in\; mathbb\{N\}$, i$<$n $Rightarrow$ (a,e_{i})$in$G_{A}, so (a,e_{(n-1)})$in$G_{A} $wedge$ (e_{(n-1)},b)$in$G_{A}, so by transitivity of G_{A}, we get (a,b)$in$G_{A}. A Contradiction of (a,b)$notin$G_{A}.

Therefore, $forall$(a,b)$in$A$times$A, (a,b)$in$T_{A} $Rightarrow$ (a,b)$in$G_{A}. This means that T$subseteq$G, for any transitive G containing R. So, T is the smallest transitive relationship containing R.

If R is transitive, then R = T.

The transitive closure of a directed acyclic graph or DAG is the reachability relation of the DAG and a strict partial order.

In computer science the concept of transitive closure can be thought of as constructing a data structure that makes it possible to answer reachability questions. That is, can one get from node a to node d in one or more hops? A binary relation tells you only that node a is connected to node b, and that node b is connected to node c, etc. After the transitive closure is constructed, as depicted in the following figure, in an O(1) operation one may determine that node d is reachable from node a. The data structure is typically stored as a matrix, so if matrix[1][4] = 1, then it is the case that node 1 can reach node 4 through one or more hops.

In computational complexity theory, the complexity class NL corresponds precisely to the set of logical sentences expressible using first-order logic together with transitive closure. This is because the transitive closure property has a close relationship with the NL-complete problem STCON for finding directed paths in a graph. Similarly, the class L is first-order logic with the commutative, transitive closure. When transitive closure is added to second-order logic instead, we obtain PSPACE.

- The transitive reduction of a relation R is the smallest relation having the transitive closure of R as its transitive closure. In general, it is not unique.

Efficient algorithms for computing the transitive closure of a graph can be found here The simplest technique is probably the Floyd-Warshall algorithm.

Wikipedia, the free encyclopedia © 2001-2006 Wikipedia contributors (Disclaimer)

This article is licensed under the GNU Free Documentation License.

Last updated on Saturday September 20, 2008 at 03:54:36 PDT (GMT -0700)

View this article at Wikipedia.org - Edit this article at Wikipedia.org - Donate to the Wikimedia Foundation

This article is licensed under the GNU Free Documentation License.

Last updated on Saturday September 20, 2008 at 03:54:36 PDT (GMT -0700)

View this article at Wikipedia.org - Edit this article at Wikipedia.org - Donate to the Wikimedia Foundation

Copyright © 2014 Dictionary.com, LLC. All rights reserved.