====== 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.
^The existence of such a node is all we need to produce a topological ordering. By induction, we can prove that a topological ordering exists.

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.