Un grafic aciclic direcționat (DAG) este un tip de grafic în care este imposibil să reveniți la același nod prin traversarea marginilor.

în teoria grafurilor, un grafic este o structură formată din noduri care sunt conectate prin margini. Vă puteți gândi la noduri ca puncte și marginile ca linii trase de la un punct la altul.

‘direcționat’ înseamnă că marginile graficului se mișcă doar într-o singură direcție, unde marginile viitoare depind de cele anterioare. De exemplu, dacă ar fi să Grafic procesul de gătit și mănâncă o masă constând din orez și pui, sarcinile implicate ar trebui să fie ordonate topologic (sau topologic sortate). Înainte de a putea mânca masa, trebuie să pregătiți mâncarea, astfel încât marginea ar fi în mod necesar îndreptată de la pregătire înainte de a mânca. Dar înainte de a putea pregăti mâncarea, trebuie să cumpărați ingredientele, așa că din nou marginea trebuie să treacă de la evenimentul anterior la evenimentul ulterior. Presupunând că orezul a fost cumpărat într-un eveniment separat de pui, ar exista două margini separate pentru evenimentele de cumpărături alimentare care nu sunt conectate între ele, dar care converg la evenimentul de preparare a mâncării.

‘aciclic’ înseamnă că este imposibil să începeți dintr-un punct al graficului și să reveniți la el urmând marginile. În timp ce un ciclu se întoarce la punctul său de plecare original ca un cerc, un grafic aciclic continuă să se miște într-o direcție liniară și nu se întoarce niciodată la punctul de plecare. Pentru a continua cu exemplul anterior de cină cu pui și orez, nu puteți trece pe grafic de la cumpărarea orezului la pregătirea mâncării până la cumpărarea puiului, deoarece acest lucru ar necesita deplasarea înapoi pe grafic. Este imposibil să pregătiți puiul dacă nu l-ați cumpărat încă.

dag-urile sunt reprezentări grafice probabilistice ale rețelelor Bayesiene care au ca scop modelarea dependenței condiționale (de exemplu, consumul mesei depinde mai întâi de pregătirea acesteia).

Mai multe criptomonede folosesc dag-uri mai degrabă decât structuri de date blockchain pentru a procesa și valida tranzacțiile. Cu blockchains, toate nodurile dintr-o rețea se bazează pe același blockchain unic, fiecare bloc făcând referire la cel care a venit înainte. Un posibil dezavantaj al acestei structuri este că pune o limită a tranzitului tranzacțiilor rețelei, deoarece există doar atât de multe tranzacții care se pot încadra într-un singur bloc și doar atât de multe blocuri care pot fi validate într-un anumit timp. Într-o rețea DAG, tranzacțiile sunt legate direct între ele, mai degrabă decât grupate în blocuri, iar Tranzacțiile pot fi procesate simultan cu altele. Rezultatul este o strangulare diminuat pe tranzitată tranzacție.