9.11. Summary of Relational Properties 359
Problem 9.25.
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.14?(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 walk
relation asD.
Hint:Considerlongestpaths between a pair of vertices.
(c)Show that if twoDAG’s have the same positive walk 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 walk relation asD.
The following examples show that the above results don’t work in general for
digraphs with cycles.
(e)Describe two graphs with verticesf1;2gwhich have the same set of covering
edges, but not the same positive walk relation (Hint:Self-loops.)
(f) (i) Thecomplete digraphwithout self-loops on vertices1;2;3has edges
between every two distinct vertices. What are its covering edges?
(ii) What are the covering edges of the graph with vertices1;2;3and edges
h 1! 2 i;h 2! 3 i;h 3! 1 i?
(iii) What about their positive walk relations?Problems for Section 9.6
Homework Problems
Problem 9.26.
Prove that ifRis a transitive binary relation on a set,A, thenRDRC.
Class Problems
Problem 9.27.
LetRbe a binary relation on a setD. Each of the following equalities and contain-
ments expresses the fact thatRhas one of the basic relational properties: reflexive,