Definition:Transitive Reduction

Relation Theory

Let $\mathcal R$ be a relation on a set $S$.

A transitive reduction of $\mathcal R$ is denoted $\mathcal R^-$, and is defined as a minimal relation on $S$ which has the same transitive closure as $\mathcal R$.

It is not guaranteed that, for a general relation $\mathcal R$, the transitive reduction is unique, or even exists.

However, if the transitive closure of $\mathcal R$ is antisymmetric and finite, then $\mathcal R^-$ exists and is unique.

Graph Theory

The same definition applies to a graph $G$.

In particular, as the formal definition of a loop-digraph is as a general relational structure, the analogy is apparent.

The concept of transitive reduction is usually encountered in the field of graph theory where it has considerable importance.