Transitive reduction
From Wikipedia, the free encyclopedia
In mathematics, the transitive reduction of a binary relation R on a set X is a minimal relation R' on X such that the transitive closure of R' is the same as the transitive closure of R. If the transitive closure of R is antisymmetric and finite, then R' is unique. However, neither existence nor uniqueness of transitive reductions is guaranteed in general.
Contents |
[edit] Example
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.
[edit] Graph algorithms for transitive reduction
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[1] tool tred provides an implementation of a depth-first search-based algorithm for finding the transitive reduction of a directed graph.
[edit] Incremental data structures
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.[2]
The algorithm uses
- O(|Enew||V|)
time for a sequence of consecutive edge insertions and
- O(|Eold||V|+|Eold|2)
time for a sequence of consecutive edge deletions, where Eold is the edge set prior to the insertions or deletions and Enew is the edge set afterwards. For acyclic graphs, the deletion algorithm requires only
- O(|Eold||V|)
time. These times are still best-known, as more recent research has preferred to focus on transitive closure.
[edit] See also
[edit] References
A. Aho, M. Garey, J. Ullman (June 1972). "The Transitive Reduction of a Directed Graph". SIAM Journal on Computing 1 (2): 131–137. doi:.
