= Topological order
A <topological order> of a finite <directed graph> $G=(V,E)$ is a <sequence> $(v_1,\ldots,v_n)$ containing every <vertex> exactly once, with
$$
(v_i,v_j)\in E\quad\Longrightarrow\quad i<j.
$$
Thus every <directed edge> points forward in the list. Equivalently, a <bijection> $p:V\to\{1,\ldots,n\}$ assigning positions satisfies $p(u)<p(v)$ for every <directed edge> $u\to v$. A <topological ordering> names the same kind of list. https://live.ocw.mit.edu/courses/6-006-introduction-to-algorithms-spring-2020/d9265b3b33d238ff914b0223ac8e7628_MIT6_006S20_r10.pdf[MIT, Recitation 10, p. 3: the edge-by-edge definition]{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\preceq 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.
Back to article page
