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:
“America is hard to see.
Less partial witnesses than he
In book on book have testified
They could not see it from outside....”
—Robert Frost (1874–1963)
“Let’s start with the three fundamental Rules of Robotics.... We have: one, a robot may not injure a human being, or, through inaction, allow a human being to come to harm. Two, a robot must obey the orders given it by human beings except where such orders would conflict with the First Law. And three, a robot must protect its own existence as long as such protection does not conflict with the First or Second Laws.”
—Isaac Asimov (1920–1992)