# 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.