\begin{slide}{Gerichtete kreisfreie Graphen -- DAGs}

Ein DAG (directed acyclic graph) ist 
\begin{itemize}
\item
  ein gerichteter Graph
\item
  ohne gerichteten Kreis.
\end{itemize}

Satz: $G$ ist DAG $\iff$ jede SCC hat nur ein Element.

DAGs entstehen u. a. beim Modellieren von Abhängigkeiten:
$x \to y$, falls (Tätigkeit/Objekt) $x$ eine Voraussetzung für $y$ ist.

Falls ein Abhängigkeitsgraph einen Kreis enthält,
sind die Abhängigkeiten nicht \glqq auflösbar\grqq.

\end{slide}
