Rettet acyklisk graf

En rettet acyklisk graf eller orienteret acyklisk graf (eng. directed acyclic graph, kaldet dag eller DAG), er i datalogien og matematikken en rettet graf uden (rettede) kredse. Dvs. for enhver knude v, er der ingen ikke-tom rettet sti, som både starter og slutter i v.

Terminologi

En kilde (source) er en knude uden indgående kanter, mens et dræn er en knude uden udgående kanter. En endelig rettet acyklisk graf har mindst en kilde og mindst et dræn.

Længden af en endelig rettet acyklisk graf, er længden (antallet af kanter) af den længste rettede sti.

Eksempler på rettede acykliske grafer

En simpel rettet acyklisk graf