Topological Orders and Linear Extensions

Orders That Respect Directed Constraints

A directed graph can record which tasks must happen before others, which events depend on earlier events, or which steps in a computation must precede later steps. An arc \(u\to v\) expresses the constraint that \(u\) comes before \(v\). A topological order is a way to list all vertices that satisfies every such constraint at once. When the constraints have more than one valid ordering, finding all of them reveals exactly which choices remain flexible.

Throughout, a digraph is finite and has directed arcs; an arc \(u\to v\) points from its tail \(u\) to its head \(v\). A directed path follows the arc directions. A directed acyclic graph, or DAG, is a digraph with no directed cycle. The empty digraph has an empty vertex set and no arcs.

Thus an arc constrains relative position, not adjacency in the list: if \(u\to v\), other vertices may appear between \(u\) and \(v\). A topological order is also called a linear ordering that respects the arcs. In a precedence model, vertices are tasks and an arc \(u\to v\) means that task \(u\) must be completed before task \(v\).

A directed path can impose a constraint even when there is no direct arc between its endpoints. For example, if \(u\to w\) and \(w\to v\), every topological order places \(u\) before \(w\) and \(w\) before \(v\), hence also places \(u\) before \(v\). This is why it is useful to compare topological orders with linear extensions of a partial order.

Reachability and Linear Extensions

For a DAG \(D=(V,A)\), define \(u\prec v\) when there is a directed path of positive length from \(u\) to \(v\). This relation records all precedence constraints forced by directed paths, not just those written as individual arcs.

Proof. We first verify the strict partial order properties. No vertex \(u\) satisfies \(u\prec u\), because such a positive-length directed path would be a directed closed walk and would contain a directed cycle. Thus the relation is irreflexive. If \(u\prec v\) and \(v\prec w\), concatenating the two directed paths gives a directed walk from \(u\) to \(w\). Removing any repeated-vertex portions gives a directed path from \(u\) to \(w\); since \(u=w\) would produce a directed cycle, the endpoints are distinct. Hence \(u\prec w\). Finally, \(u\prec v\) and \(v\prec u\) would concatenate to a directed closed walk of positive length, which contains a directed cycle. This is impossible in a DAG. So the relation is transitive and no two distinct vertices precede each other in both directions.

Now suppose a listing is a topological order. Along every arc, the tail occurs before the head. Along a directed path, applying this fact successively shows that its first vertex occurs before its last vertex. Therefore the listing respects every pair \(u\prec v\), so it is a linear extension. Conversely, every arc \(u\to v\) is itself a directed path of length one, so \(u\prec v\). A linear extension must therefore place \(u\) before \(v\) for every arc, which is precisely the definition of a topological order. \(\square\)

There is also a simple necessary condition for a topological order that applies to any digraph: it cannot contain a directed cycle. If a directed cycle has vertices \(v_1,\ldots,v_k\) in cyclic order, its arcs would require \(v_1\) before \(v_2\), \(v_2\) before \(v_3\), and so on, with \(v_k\) before \(v_1\). These requirements cannot all hold in a linear listing. This obstruction is useful when checking whether a precedence model is consistent.

Enumerating All Valid Orders

For a small digraph, one reliable way to enumerate orders is to build each listing from left to right. At every step, choose a vertex whose required predecessors have already appeared. A required predecessor of \(v\) is any vertex \(u\) with a directed path to \(v\); checking just the direct incoming arcs also works if all those constraints have already been respected. If no vertices remain, the listing is complete. If a choice branches, explore each choice. This is an enumeration method for small examples, not a claim that listing all orders is efficient for large digraphs.

Why the Orders Matter—and a Common Pitfall

Topological orders make precedence information concrete. One order is a possible schedule when tasks have no additional restrictions such as durations or resource limits. Multiple orders indicate that some tasks can be rearranged without violating the stated constraints. The reachability partial order separates forced precedence from incidental choices: if neither \(u\prec v\) nor \(v\prec u\), the constraints do not force either one to precede the other, although other tasks may still affect where they can appear in a full listing.

A frequent counting error is to treat independent chains as indivisible blocks. For the digraph in the third example, one might regard \(a,c\) as a block and \(b,d\) as a block, then count only two orders: \(a,c,b,d\) and \(b,d,a,c\). That calculation wrongly excludes interleavings such as \(a,b,c,d\). The correction is to preserve the order within each chain while allowing their elements to interleave; choosing the two positions for \(a,c\) gives \(\binom{4}{2}=6\) orders.

Another useful check is to test every arc, not just the first and last entries or a few sample constraints. A proposed listing is valid exactly when every arc’s tail has a smaller position than its head. For a DAG, it is equivalent to check all reachability constraints, but checking the arcs is enough because the inequalities along a directed path force the corresponding endpoint inequality.