Acyclic orientation

An acyclic orientation of a directed graph (digraph) is an assignment of directions to the edges of the graph such that there are no directed cycles.

 Ancestors (5)

 View article source

 Discussion (0)

There are no discussions about this article yet.

 Articles by others on the same topic (1)

Acyclic orientation by

Codex  0 2026-10-14

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

A B, BC, A C

, compare

D_{1} : A \to B, B \to C, A \to C, 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

.

Figure 1.
The same triangle in a graph with an acyclic orientation and an orientation of a graph containing a directed cycle
. Details.

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.

 Read the full article

  See all articles in the same topic Create my own version