Definition:Transitive Reduction/Graph Theory
Jump to navigation
Jump to search
Definition
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$.
Also see
- Results about transitive reductions can be found here.