Orienteret acyklisk graf

Fra Wikipedia, den frie encyklopædi
Gå til: navigation, søg

En orienteret acyklisk graf (eng. directed acyclic graph, kaldet dag eller DAG), er inden for datalogien og matematikken en orienteret graf uden orienterede kredse. Dvs. for enhver knude v, er der ingen ikke-tom orienteret sti, som både starter og slutter i v.

Terminologi[redigér | redigér wikikode]

En kilde (source) er en knude uden indgående kanter, mens en sink er en knude uden udgående kanter. En endelig DAG har mindst en kilde og mindst en sink.

Længden af en endelig DAG, er længden (antallet af kanter) af den længste orienterede sti.

Eksempler på orienterede acykliske grafer[redigér | redigér wikikode]

Dag graf.JPG
En simpel orienteret acyklisk graf