Acyclic orientation

An acyclic orientation is an orientation of a graph whose resulting directed graph has no directed cycle, hence is a Directed acyclic graph. A directed cycle must follow every arrow around its closed route. A cycle in a graph in the skeleton of a directed graph only requires the corresponding undirected edges; their arrows need not agree around the route.

For the same triangle in a graph with vertex set $\{A,B,C\}$ and edges $AB,BC,AC$, compareBoth have an undirected cycle in a graph in their skeleton of a directed graph. Only $D_2$ has a directed cycle. In $D_1$, $C$ has no outgoing directed edge, so a route cannot continue from $C$ back to $A$.

Thus an acyclic orientation does not require its underlying undirected graph to be a forest. Every orientation of a graph of a forest is acyclic, because a directed cycle would give an undirected cycle in a graph. Conversely, every finite simple graph, including one with many cycles in a graph, admits at least one acyclic orientation by the following ordering construction. On this triangle in a graph, six of the eight orientations of a graph are acyclic; the other two follow the directed cycle in opposite senses.

Choose a strict total order $v_1<\cdots <v_n$ of the vertices of a finite simple graph. Direct every edge $v_i{v}_j$ from $v_i$ to $v_j$ when $i<j$. Along every directed path, the index strictly increases. Returning to the starting vertex would require an impossible strict increase back to the initial index, so this is an acyclic orientation. The displayed $D_1$ comes from $A<B<C$.

The chosen strict total order is a topological order of the resulting Directed acyclic graph. Conversely, every acyclic orientation of a finite simple graph has a topological order, and orienting its edges from earlier to later in that order recovers it. Different topological orders can induce the same acyclic orientation, since vertices with no edge between them need not impose a choice of arrow.^[ref]

An order respects reachability but does not create it: $u<v$ in a chosen topological order does not imply a directed path from $u$ to $v$. For example, orient the two edges of the graph path $A,B,C$ using $A<C<B$. The arrows are $A\to B$ and $C\to B$; there is no directed path from $A$ to $C$, despite $A<C$. In $D_1$, however, $A$ reaches $C$ both directly and via $B$. Following outgoing directed edges with graph search decides this directional reachability.^[ref]