DAGs and Partial Orders
The reachability relation of a directed acyclic graph is a partial order; any partial order may be defined in this way, for instance as the reachability relation of its transitive reduction. If a directed graph is not acyclic, its reachability relation will be a preorder but not a partial order.
Read more about this topic: Reachability
Famous quotes containing the words partial and/or orders:
“It is characteristic of the epistemological tradition to present us with partial scenarios and then to demand whole or categorical answers as it were.”
—Avrum Stroll (b. 1921)
“One cannot be a good historian of the outward, visible world without giving some thought to the hidden, private life of ordinary people; and on the other hand one cannot be a good historian of this inner life without taking into account outward events where these are relevant. They are two orders of fact which reflect each other, which are always linked and which sometimes provoke each other.”
—Victor Hugo (1802–1885)