Rettet acyklisk graf

Fra Wikipedia, den frie encyklopædi
Spring til navigation Spring til søgning

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.

Eksempler på rettede acykliske grafer[redigér | rediger kildetekst]

Dag graf.JPG
En simpel rettet acyklisk graf