Cycles · Acyclic Graphs

Lesson 4

Nikolai Chukhin · Alexander S. Kulikov

It is not difficult to see that for the graph above, there is no topological ordering, because it contains a cycle (\(1 \to 5 \to 4 \to 3 \to 1\)). Going back to the dependency graph, a cycle is indeed an anomaly that prevents one from being able to process jobs one by one without violating some precedence constraint. At this point, it is natural to ask:

For what graphs does a topological ordering exist?

As we discussed above, a cycle in a graph is a clear obstacle. Thus, our question can be restated as follows: are there other obstacles?

We show below that no other obstacle exists! In the proof, we use a notion of a sink. In a directed graph, a sink is a node with no outgoing edges.

For example, the sinks of the graph below are the nodes 2, 3, and 7.

It turns out that every DAG has at least one sink.