= Acyclic orientation
{wiki}
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$, compare
$$
D_1:\ A\to B,\ B\to C,\ A\to C,
\qquad
D_2:\ A\to B,\ B\to C,\ C\to A.
$$
Both 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$.
\Image[/graph-orientation-triangle-acyclic-versus-cyclic.png]
{title=The same <triangle in a graph> with an <acyclic orientation> and an <orientation of a graph> containing a <directed cycle>}
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.
Back to article page
