info prev up next book cdrom email home

Transitive Reduction

The transitive reduction of a binary Relation $R$ on a Set $X$ is the minimum relation $R'$ on $X$ with the same Transitive Closure as $R$. Thus $a R' b$ for any elements $a$ and $b$ of $X$, provided that $a R b$ and there exists no element $c$ of $X$ such that $a R c$ and $c R b$.

See also Reflexive Reduction, Transitive Closure

© 1996-9 Eric W. Weisstein