With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

No credit card required

Chapter Nineteen 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 `s` to `t`, but provides no information about whether or not there is an edge from `t` to `s`. There are four different ways in which two vertices might be related in a digraph: no edge; an edge `s-t` from `s` to `t`; an edge `t-s` from `t` to `s`; or two edges `s-t` and `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; ...

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

No credit card required