Category:Definitions/Transitive Reductions

From ProofWiki
Jump to navigation Jump to search

This category contains definitions related to Transitive Reductions.
Related results can be found in Category:Transitive Reductions.


Relation Theory

Let $\RR$ be a relation on a set $S$.


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


Graph Theory

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


Let $G = \struct {V, E}$ be a loop-digraph.

Let $G$ be expressed formally as a relational structure $\GG$.

A transitive reduction of $G$ is denoted $G^-$, and is defined as a transitive reduction of the relation $\GG$.

Hence it is a minimal loop-digraph on $V$ which has the same transitive closure as $\GG$.

Pages in category "Definitions/Transitive Reductions"

The following 4 pages are in this category, out of 4 total.