Rettet asyklisk graf
Denne artikkelen mangler kildehenvisninger, og opplysningene i den kan dermed være vanskelige å verifisere. Kildeløst materiale kan bli fjernet.
En rettet asyklisk graf (engelsk: directed acyclic graph, kalt DAG eller dag ), er innenfor informatikken og matematikken navnet på en endelig rettet graf uten rettede sykluser. For hver node v er det ingen ikke-tom rettet sti som både starter og slutter i v.
En kilde (source) er en node uten inngående kanter, mens en sink er en node uten utgående kanter. En endelig DAG har minst en kilde og minst en destinasjon (sink). Lengden på en endelig DAG, er lengden (antall kanter) av den lengste rettede sti.
Eksempler på rettede asykliske grafer[rediger | rediger kilde]
