Gerichtete kreisfreie Graphen - DAGs

Ein DAG (directed acyclic graph) ist

• ein gerichteter Graph
• ohne gerichteten Kreis.

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 ,,auflösbar``.