Directed Acyclic Graphs

Why

If a directed graph has no cycles, then it has a nice property.¹

Definition

Directed and acyclic graphs (or directed acyclic graphs, DAGs) have partial ordering property on vertices. We call a vertex $s$ an ancestor of a vertex $u$ if there is a directed path from $s$ to $u$.

Partial Order

We call a vertex $s$ and ancestor of a vertex $t$ if there is a directed path from $s$ to $t$. The relation $R$ defined by $(s, t) \in R$ if $s$ is an ancestor of $t$ is a partial order.

Clearly, every subgraph induced on a directed acyclic graph is a directed acyclic graph.

Let $(V, E)$ be a directed acyclic graph. Then there exists a vertex $v \in V$ which is a source and a vertex $w \in V$ which is a sink.

There exists a directed path of maximum length. It must start at a source and end at a sink.²

Topological numbering

We can choose a total ordering that is consistent with the partial order of ancestry.

A topological numbering (or topological sort, topological ordering) of a directed graph $(V, E)$ is a numbering $\sigma : \set{1, \dots , \num{V}} \to V$ satisfying

\[ (v, w) \in E \implies \inv{\sigma }(v) < \inv{\sigma }(w). \]

There exists a topological sort for every acyclic graph.

Let $(V, F)$ be a directed acyclic graph. There exists a source vertex, $v_1$. Set $\sigma (1) = v_1$. Take the subgraph induced by $V - \set{v_1}$. It is directed acyclic, and so has a source vertex, $v_2$. Set $\sigma (2) = v_2$. Continue in this way.⁴

Future editions will expand this vague introduction. ↩︎
Future editions will expand. ↩︎
Future editions will further explain this concept. ↩︎
Future editions will clarify and expand. ↩︎