Transitive reduction

From formulasearchengine
Jump to navigation Jump to search

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

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).

Tred-G.png Tred-Gprime.png

The transitive reduction of a finite directed acyclic graph is unique.

The transitive reduction of a finite partially ordered set is its covering relation, which is given visual expression by means of a Hasse diagram.

Graph algorithms for transitive reduction

The transitive reduction of an acyclic relation can be computed using its transitive closure :

Here, denotes relation composition.

Template:Harv, which introduced the term in this meaning, also proves a connection between transitive closure and reduction:

  • they extend the computation of transitive reduction from transitive closure to deal with cycles;
  • they give a construction to compute a graph's transitive closure from its transitive reduction;
  • thus, transitive closure and transitive reduction have the same time complexity.

The tred tool in the Graphviz[1] toolset transitively reduces a graph, using a depth-first search-based implementation.

Incremental data structures

One of the most well-studied problemsTemplate:Cn 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 Jan 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.Template:Cn

See also

References

Notes

General references

  • {{#invoke:Citation/CS1|citation

|CitationClass=journal }}

External links


de:Transitive Reduktion uk:Транзитивне скорочення