Topological order

A topological order of a finite directed graph $G=(V,E)$ is a sequence $(v_1,\dots ,v_n)$ containing every vertex exactly once, withThus every directed edge points forward in the list. Equivalently, a bijection $p:V\to \{1,\dots ,n\}$ assigning positions satisfies $p(u)<p(v)$ for every directed edge $u\to v$. A topological ordering names the same kind of list. ^[ref]

The toy Directed acyclic graph has exactly five topological orders: $ABCDE$, $ABDCE$, $ACBDE$, $BACDE$, and $BADCE$. These lists were checked by enumerating all $5!=120$ permutations and retaining precisely those satisfying all five directed edge inequalities. Every list ends with $E$, since all other tasks have a directed path to publication. A topological order need not put adjacent entries next to one another in the directed graph: $A$ and $B$ are consecutive in $ABCDE$ without a directed edge between them.

A directed cycle would force the impossible chain of position inequalities $p(u_1)<p(u_2)<\cdots <p(u_k)<p(u_1)$. In the toy example, adding $E\to C$ requires review before publication and publication before review, so there are no topological orders. Together with the construction in topological sorting, this proves that a finite directed graph admits a topological order if and only if it is a Directed acyclic graph. The empty directed graph has the empty sequence as its topological order.

There is also a useful connection to partial orders: define $u⪯v$ when $u=v$ or there is a directed path from $u$ to $v$. For a Directed acyclic graph, this reachability relation is a partial order, and its linear extensions are exactly the topological orders. The Directed acyclic graph specifies which pairs must be ordered; a topological order chooses positions for all the remaining pairs.