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
[redigér | rediger kildetekst]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.