(
graph theory):
An orientation of an undirected graph is an assignment of a direction to each edge. Formally, an orientation is a function f:E->V, where E is the edge set of the graph and V is the vertex set of the graph, such that every edge is mapped to a vertex to which it is incident. This changes an undirected graph into a directed graph (a digraph).
An acyclic orientation is an orientation which has no cycles - that is, no path on the graph can end up where it started if it must follow the edge directions. The number of acyclic orientations of a graph is given by evaluating the chromatic polynomial of the graph at x = -1. [Stanley, 1978]
An example of a cyclic (i.e. not acyclic) orientation of C4 is:
*-->---*
| |
^ v
| |
*--<---*