Lesson 2

A typical application of directed graphs is to model precedence constraints. In this case, nodes are jobs and there is a directed edge from \(A\) to \(B\) if the job \(A\) must be processed before the job \(B\).

Assume that we would like to process jobs one by one so that all the precedence constraints are satisfied (that is, whenever there is an edge \((A,B)\), we process the job \(A\) before the job \(B\)). This leads us to the following important definition. A topological ordering of a directed graph is a permutation \((v_{1}, …, v_{n})\) of its vertices such that, for any edge \(v_{i} \to v_{j}\), it follows that \(i \leq j\) in that ordering.

For example, \((2, 1, 6, 5, 4, 3)\) is a topological ordering of the graph below. \((2, 1, 5, 4, 6, 3)\) is another topological ordering (hence, there may exist more than one topological ordering).

A convenient way of visualizing it is to place all nodes on a line according to the ordering and to draw all edges of the graph. Then, all edges must go from left to right.