Chapter 19. Digraphs and DAGs
When we attach significance to the order in which the two vertices are specified in each edge of a graph, we have an entirely different combinatorial object known as a digraph, or directed graph. Figure 19.1 shows a sample digraph. In a digraph, the notation
s-t describes an edge that goes from
t but provides no information about whether or not there is an edge from
s. There are four different ways in which two vertices might be related in a digraph: no edge; an edge
t; an edge
s; or two edges
t-s, which indicate connections in both directions. The one-way restriction is natural in many applications, easy to enforce in our implementations, and seems innocuous; but it implies ...