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; ...