Orienteret acyklisk graf
Fra Wikipedia, den frie encyklopædi
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.
[redigér] Terminologi
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.


