9.12. Summary of Relational Properties 259
Path-Total Rispath-totalwhen
8 x¤y 2 A: .x R y ORy R x/Given any two vertices inR, there is an edge in one direction or the other
between them.
For any finite, nonempty set of vertices ofR, there is a directed path going
through exactly these vertices.Strict Partial OrderRis astrict partial orderiffRis transitive and asymmetric
iffRis transitive and irreflexive.
Weak Partial Order Ris aweak partial orderiff it is transitive and anti-symmetric
and reflexive.
Problems for Section 9.5
Practice Problems
Problem 9.1. (a)Why is every strict partial order a DAG?
(b)Give an example of a DAG that is not a strict partial order.(c)Why is the positive path relation of a DAG a strict partial order?Class Problems
Problem 9.2.
Ifaandbare distinct nodes of a digraph, thenais said tocoverbif there is an
edge fromatoband every path fromatobincludes this edge. Ifacoversb, the
edge fromatobis called acovering edge.
(a)What are the covering edges in the DAG in Figure 9.10?(b)Let covering.D/be the subgraph ofDconsisting of only the covering edges.
SupposeDis a finite DAG. Explain why covering.D/has the same positive path
relation asD.
Hint:Considerlongestpaths between a pair of vertices.
(c)Show that if twoDAG’s have the same positive path relation, then they have
the same set of covering edges.
(d)Conclude that covering.D/is theuniqueDAG with the smallest number of
edges among all digraphs with the same positive path relation asD.