= Unique topological ordering criterion
A finite nonempty <Directed acyclic graph> has a unique <topological sort> exactly when it has a <Hamiltonian path>. A <Hamiltonian path> forces the relative order of every consecutive pair and therefore of all <vertices>. Conversely, in a unique <topological sort>, every consecutive pair must have a forward edge: if such an edge were absent, swapping that adjacent pair would preserve all edge constraints and produce a second <topological sort>. The consecutive edges give a <Hamiltonian path>. Consequently one may compute any <topological sort> and test its consecutive edges, taking $O(n^2)$ time on an <adjacency matrix> representation.
Back to article page
