en riktad acyklisk Graf (DAG) är en typ av graf där det är omöjligt att komma tillbaka till samma nod genom att korsa kanterna.

i grafteori är en graf en struktur som består av noder som är förbundna med kanter. Du kan tänka på noderna som punkter och kanterna som linjer ritade från punkt till punkt.

’riktad’ betyder att grafens kanter bara rör sig i en riktning, där framtida kanter är beroende av tidigare. Om du till exempel skulle kartlägga processen med att laga mat och äta en måltid bestående av ris och kyckling, skulle de berörda uppgifterna behöva topologiskt beställas (eller topologiskt sorteras). Innan du kan äta måltiden måste du förbereda maten, så kanten skulle nödvändigtvis riktas från förberedelse fram till att äta. Men innan du kan laga maten måste du köpa ingredienserna, så igen måste kanten gå från den tidigare händelsen till den senare händelsen. Om man antar att riset köptes i en separat händelse från kycklingen skulle det finnas två separata kanter för dagligvaruhandeln som inte är kopplade till varandra, men som konvergerar vid beredningen av maten.

’acyklisk’ betyder att det är omöjligt att starta vid en punkt i diagrammet och komma tillbaka till det genom att följa kanterna. Medan en cykel kommer tillbaka till sin ursprungliga utgångspunkt som en cirkel, fortsätter en acyklisk graf att röra sig i linjär riktning och cirklar aldrig tillbaka till utgångspunkten. För att fortsätta med det tidigare exemplet på kyckling-och rismiddag kan du inte flytta på grafen från att köpa riset till att förbereda maten för att köpa kycklingen, eftersom det skulle kräva att du flyttar bakåt över grafen. Det är omöjligt att förbereda kycklingen om du ännu inte har köpt den.

Dagsär probabilistiska grafiska representationer av bayesiska nätverk som syftar till att modellera villkorligt beroende (t.ex. att äta måltiden beror på att förbereda den först).

flera cryptocurrencies använder DAGs snarare än blockchain datastrukturer för att bearbeta och validera transaktioner. Med blockchains bygger alla noder i ett nätverk på samma enda blockchain med varje block som refererar till den som kom före den. En möjlig nackdel med denna struktur är att den sätter en gräns för nätverkets transaktionsflöde, eftersom det bara finns så många transaktioner som kan passa i ett enda block och bara så många block som kan valideras under en viss tid. I ett DAG-nätverk är transaktioner direkt kopplade till varandra snarare än grupperade i block, och transaktioner kan behandlas samtidigt med andra. Resultatet är en minskad flaskhals på transaktionsflödet.