Digrafo aciclico: differenze tra le versioni

 

In [[matematica]] e [[informatica]] un '''grafo aciclico diretto''' oppure '''grafo aciclico orientato''' (in [[lingua inglese|inglese]] ''Directed acyclic graph'', DAG) è un particolare tipo di [[Digrafo (matematica)|digrafo]] (anche noto come "grafo diretto") che non ha [[Ciclo_(teoria_dei_grafi)#Ciclo|cicli]] (circuiti) diretti, ovvero comunque scegliamo un [[Vertice (teoria dei grafi)|vertice]] del grafo non possiamo tornare ad esso percorrendo gli [[Arco (teoria dei grafi)|archi]] del grafo.

 

I DAG sono usati per rappresentare diversi tipi di strutture sia in matematica che in informatica. Per esempio una serie di lavori che devono essere ordinati in modo tale che alcuni di essi debbano essere eseguiti prima di altri (per esempio le applicazioni da eseguire durante l'avvio di un computer) possono essere rappresentati con un DAG dove ogni vertice rappresenta un lavoro e ogni arco la relazione di dipendenza, cioè se c'è un arco che va da ''A'' a ''B'' vuol dire che ''A'' deve essere eseguito prima di ''B''; l'algoritmo per l'[[ordinamento topologico]] rappresenta una buona soluzione al problema. I DAG possono anche essere usati per rappresentare in modo efficiente una serie di sequenze che si sovrappongono.