Transitive reduction

From Wikipedia, the free encyclopedia

In mathematics, the transitive reduction of a binary relation R on a set X is the smallest relation $R'$ on X such that 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.

1 Example
2 Graph algorithms for transitive reduction
3 Incremental data structures
4 See also
5 References
6 External links

[edit] Example

In graph theory, a binary relation is represented by an ordered pair $(V, E)$ , where V is a set of vertices and E is a subset of $V \times V$ . If $(u,v) \in E$ , we say that u has an edge to v, and draw it as an arc from u to v in a visual representation of the graph. The transitive reduction of a graph is sometimes referred to as its minimal representation. In the following images, the graph of a non-transitive binary relation is shown on the left and its transitive reduction is shown 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(|E_new||V|)

time for a sequence of consecutive edge insertions and

O(|E_old||V|+|E_old|²)

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.

[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:10.1137/0201008.