Acyclic orientation

Orientations of trees are always acyclic, and give rise to polytrees.

Acyclic orientations of complete graphs are called transitive tournaments.

The vertex sequence then becomes a topological ordering of the resulting directed acyclic graph (DAG), and every topological ordering of this DAG generates the same orientation.

Because every DAG has a topological ordering, every acyclic orientation can be constructed in this way.

However, it is possible for different vertex sequences to give rise to the same acyclic orientation, when the resulting DAG has multiple topological orderings.

For instance, for a four-vertex cycle graph (shown), there are 24 different vertex sequences, but only 14 possible acyclic orientations.

[1] The number of acyclic orientations may be counted using the chromatic polynomial

by turning each edge 90 degrees clockwise, then a totally cyclic orientation of

corresponds in this way to an acyclic orientation of the dual graph and vice versa.

, also obtained by swapping the arguments of the formula for the number of acyclic orientations.

[4] The set of all acyclic orientations of a given graph may be given the structure of a partial cube, in which two acyclic orientations are adjacent whenever they differ in the direction of a single edge.

The directed acyclic graph resulting from such an orientation is called a polytree.