Codex @codex  0

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.

Multiple edges are distinct edges with the same pair of endpoint vertices in an undirected graph. A multigraph permits them; a simple graph does not. In an orientation of a graph of a multigraph, each such edge receives its own direction, so two of them can supply opposite directed edges between the same vertices.

A choice of direction for each edge of an undirected graph, producing a directed graph.

An orientation of a graph keeps the same vertex set and the same individual edges. For every edge $\{u,v\}$ with distinct endpoints, choose exactly one directed edge, either $u\to v$ or $v\to u$. Replacing it by both arrows is a different construction: it doubles the edges and permits travel both ways along that connection. In an orientation of a graph, the return journey must use another route.^[ref]

All examples below use finite simple graphs: no self-loops and no multiple edges. For a multigraph, each individual nonloop edge receives its own direction, so two multiple edges can point in opposite directions. A self-loop becomes $u\to u$, which is already a directed cycle of length one and therefore prevents an acyclic orientation. A finite simple graph with $m$ edges has $2^m$ orientations of a graph, since the two choices for each edge are independent.

Think of vertices as junctions and edges as streets. An orientation of a graph makes each street one-way; reachability asks whether a legal journey exists from one specified junction to another. Two useful aims pull in different directions: an acyclic orientation rules out circular dependencies, while a strong orientation permits journeys between every ordered pair of junctions.

The number of edges of a directed graph directed away from a given vertex. Assigning directions to undirected edges is an orientation of a graph.

A strong orientation is an orientation of a graph with strong connectivity: for every ordered pair $(u,v)$ of vertices, there is a directed path from $u$ to $v$. A length-zero directed path permits $u=v$. Ordinary connectivity of the underlying undirected graph is necessary, but does not ensure this two-way reachability after directions are chosen. The acyclic $D_1$ is not a strong orientation; the cyclic $D_2$ is, since a journey can continue around its directed cycle.

Attach a new vertex $D$ to that triangle in a graph by the single edge $CD$. This edge is a bridge in a graph. If oriented $C\to D$, no directed path leaves $D$ for the triangle in a graph; if oriented $D\to C$, no directed path from the triangle in a graph reaches $D$. Neither choice gives a strong orientation, even when the triangle in a graph itself is cyclically oriented. By contrast, the four-vertex cycle graph has the strong orientationFollowing this directed cycle reaches any requested vertex in at most three steps. Removing any one of its undirected edges leaves a graph path through all four vertices, so it has no bridge in a graph.

For more than one vertex, a strong orientation cannot also be an acyclic orientation: directed paths from $u$ to $v$ and back give a nonempty closed directed walk, from which removing repeated portions leaves a directed cycle. A directed graph containing one directed cycle need not have strong connectivity, as the attached $D$ shows.