= Reachability preorder
{title2=$u\preceq v\iff\text{a directed path from }u\text{ to }v\text{ exists}$}
Reachability in a <directed graph>, allowing length-zero paths, is a <preorder>: zero steps give reflexivity and concatenation gives transitivity. Distinct mutually reachable vertices violate <antisymmetry>. Its equivalence classes under mutual reachability are the <strongly connected components>; the induced reachability relation on those classes is a <partial order>. Equivalently, contracting the classes gives the acyclic <condensation graph>.
Back to article page
