Added to Favorites

Popular Searches

Definitions

In mathematics, the transitive reduction of a binary relation R on a set X is a minimal relation $R\text{'}$ on X such that the transitive closure of $R\text{'}$ is the same as the transitive closure of R. If the transitive closure of R is antisymmetric and finite, then $R\text{'}$ is unique. However, neither existence nor uniqueness of transitive reductions is guaranteed in general.
## Example

## Graph algorithms for transitive reduction

## Incremental data structures

## See also

## References

A. Aho, M. Garey, J. Ullman (1972). "The Transitive Reduction of a Directed Graph". *SIAM Journal on Computing* 1 (2): 131–137.
## External links

In graph theory, any binary relation R on a set X may be thought of as a directed graph (V, A), where V = X is the vertex set and A = R is the set of arcs of the graph. The transitive reduction of a graph is sometimes referred to as its minimal representation. The following image displays drawings of graphs corresponding to a non-transitive binary relation (on the left) and its transitive reduction (on the right).

The transitive reduction of a finite acyclic graph is unique. For a graph with nontrivial strongly connected components, each such component will become a cycle in any transitive reduction of that graph. More formally, suppose we have a graph G and we form an acyclic graph G' by contracting each strongly connected component to a vertex. If we take the unique transitive reduction of G', then expand each vertex back out to a cycle containing the vertices contracted to form it, attaching incident edges at any vertex in the cycle, the result will be a minimal transitive reduction regardless of how this expansion is performed.

In 1972, it was shown by Aho, Garey, and Ullman that algorithms for transitive reduction have the same time complexity as algorithms for transitive closure.

The graphviz tool tred provides an implementation of a depth-first search-based algorithm for finding the transitive reduction of a directed graph.

One of the most well-studied problems in computational graph theory is that of incrementally keeping track of the transitive closure of a graph while performing a sequence of insertions and deletions of vertices and edges. In 1987, J.A. La Poutré and J. van Leeuwen described in their well-cited Maintenance Of Transitive Closures And Transitive Reductions Of Graphs an algorithm for simultaneously keeping track of both the transitive closure and transitive reduction of a graph in this incremental fashion.

The algorithm uses

- O(|E
_{new}||V|)

time for a sequence of consecutive edge insertions and

- O(|E
_{old}||V|+|E_{old}|^{2})

time for a sequence of consecutive edge deletions, where E_{old} is the edge set prior to the insertions or deletions and E_{new} is the edge set afterwards. For acyclic graphs, the deletion algorithm requires only

- O(|E
_{old}||V|)

time. These times are still best-known, as more recent research has preferred to focus on transitive closure.

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 04:54:49 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 04:54:49 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.