Rettet asyklisk graf

Fra Wikipedia, den frie encyklopedi
Jump to navigation Jump to search

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 der ingen ikke-tom retted 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 sink. Lengden på en endelig DAG, er lengden (antall kanter) av den lengste rettede sti.

Eksempler på rettede asykliske grafer[rediger | rediger kilde]

Dag graf.JPG
En enkel rettet asyklisk graf