Reachability - DAGs and Partial Orders

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:

    “You must not be partial in judging: hear out the small and the great alike; you shall not be intimidated by anyone, for the judgment is God’s.”
    —Bible: Hebrew, Deuteronomy 1:17.

    “Our own physical body possesses a wisdom which we who inhabit the body lack. We give it orders which make no sense.”
    —Henry Miller (1891–1980)