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
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.