Directed acyclic graph

A directed acyclic graph (DAG) is a directed graph that contains no cycles. DAGs arise in a natural way in modelling situations in which, in some sense, going "forward" is sometimes possible but going "backward" is definitely not, so that if $v$ is reachable from $u$, we know that $u$ is not reachable from $v$ (unless $u = v$). An example is given by Water Park from CCC 2007. In the absence of mechanical intervention, water always flows from high altitudes to low altitudes, so that, when travelling along the waterslides, one can never arrive at the same spot twice. If we create a graph that has a vertex for each marked point in the water park and a directed edge from $u$ to $v$ whenever there is a water slide from $u$ to $v$, this graph will be acyclic, and hence a DAG. DAGs do not necessarily resemble undirected acyclic graphs (that is, forests) in form or in their properties; there may be multiple paths between a given pair of nodes.

As a partial order

DAGs are often considered representations of partial orderings. We can establish a correspondence as follows:

1. Give each vertex of the DAG a unique label (such as the letters A, B, C, etc.). Each label corresponds to an element in our set.
2. We define our partial ordering as follows: $a \leq b$ in the ordering if and only if there exists a path from $u$ to $v$, where $u$ is the vertex in the DAG labelled with $a$ and $v$ is the vertex in the DAG labelled with $b$.

The ordering thus defined is reflexive, since every vertex is reachable from itself. It is antisymmetric, because if $u \leq v$ and $v \leq u$, and $u \neq v$, then we have a cycle that contains $a$ and $b$, a contradiction. And it is transitive because reachability is transitive; if there are paths from $u$ to $v$ and from $v$ to $w$ then we can concatenate them to obtain a path from $u$ to $w$. So the ordering we have defined is a partial ordering.

Note that whereas a given DAG will correspond to exactly one partial ordering (up to isomorphism) using this convention, there may be more than one DAG that corresponds to a given partial ordering. The DAG with the greatest number of edges that corresponds to a given partial ordering is known as the transitive closure, whereas the one with the fewest number of edges is known as the transitive reduction.