Chapter 3.6: Directed Acyclic Graphs & Topological Ordering

A directed graph with no cycles is called (obviously) a directed acyclic graph (DAG). DAGs can be used to encode precedence relations or dependencies. For example, if there are a set of tasks {1,2,…,n} that need to be performed and there are dependencies among them (i.e. for a pair i and j, i must be performed before j) then a DAG would be a way to represent those tasks. Each task can be a node, and there is a directed edge (i,j) whenever i must be done before j. If there is a cycle in the graph, there would be no way to do any of the tasks in that cycle since no task could ever be done first. A valid order for which the tasks could be performed with all of the dependencies respected is called a topological ordering. A topological ordering for a graph G is an ordering of its nodes as v_1, v_2,…, v_n so that for every edge (v_i, v_j) we have i<j. In other words, all edges point forward in the ordering.

If G has a topological ordering, then G is a DAG. In every DAG G, there is a node v with no incoming edges.

If G is a DAG, then G has a topological ordering.

I would rate this section an 8. It was easy to read, but I think the lecture was easier to understand than this chapter.