Page "Preorder" Paragraph 16

* The reachability relationship in any directed graph ( possibly containing cycles ) gives rise to a preorder, where x ≤ y in the preorder if and only if there is a path from x to y in the directed graph.

Conversely, every preorder is the reachability relationship of a directed graph ( for instance, the graph that has an edge from x to y for every pair ( x, y ) with x ≤ y ).

However, many different graphs may have the same reachability preorder as each other.

In the same way, reachability of directed acyclic graphs, directed graphs with no cycles, gives rise to partially ordered sets ( preorders satisfying an additional anti-symmetry property ).