Az irányított aciklikus gráf (DAG) egy olyan gráftípus, amelyben lehetetlen ugyanarra a csomópontra visszatérni az élek áthaladásával.

a gráfelméletben a gráf olyan struktúra, amely csomópontokból áll, amelyeket élek kötnek össze. A csomópontokat pontként, az éleket pedig pontról pontra rajzolt vonalakként lehet értelmezni.

“irányított” azt jelenti, hogy a gráf élei csak egy irányban mozognak, ahol a jövőbeli élek a korábbiaktól függenek. Ha például a rizsből és csirkéből álló szakács-és étkezésfolyamatot kellene feltérképezni, akkor az érintett feladatokat topológiailag (vagy topológiailag rendezve) kellene elvégezni. Mielőtt enni az ételt, elő kell készítenie az ételt, így a szél szükségszerűen az előkészítéstől az étkezésig irányul. De mielőtt elkészítheti az ételt, meg kell vásárolnia az összetevőket, így a szélnek ismét a korábbi eseményről a későbbi eseményre kell mennie. Tegyük fel, hogy a rizst a csirkétől külön eseményen vásárolták meg, két külön él lenne az élelmiszerbolt-vásárlási eseményekhez, amelyek nem kapcsolódnak egymáshoz, de amelyek az étel elkészítésekor konvergálnak.

“aciklikus” azt jelenti, hogy lehetetlen a gráf egy pontján elindulni, és a szélek követésével visszatérni hozzá. Míg egy ciklus visszatér az eredeti kiindulási pontjához, mint egy kör, egy aciklikus gráf továbbra is lineáris irányban mozog, és soha nem tér vissza a kiindulási ponthoz. A csirke-és rizsvacsora korábbi példájának folytatásához nem lehet a grafikonon mozogni a rizs megvásárlásától az étel elkészítéséig a csirke megvásárlásáig, mivel ehhez visszafelé kell haladnia a grafikonon. Lehetetlen előkészíteni a csirkét, ha még nem vásárolta meg.

A DAGs a bayesi hálózatok valószínűségi grafikus ábrázolásai, amelyek célja A feltételes függőség modellezése (például az étkezés elfogyasztása az első elkészítésétől függ).

Több kriptovaluta dag-okat használ a blockchain adatstruktúrák helyett a tranzakciók feldolgozásához és érvényesítéséhez. A blockchains segítségével a hálózat összes csomópontja ugyanazon az egyetlen blokkláncon épül fel, mindegyik blokkkal utalva az előtte lévőre. Ennek a struktúrának az egyik lehetséges hátránya, hogy korlátozza a hálózat tranzakciós teljesítményét, mivel csak annyi tranzakció van, amely egyetlen blokkba illeszkedik, és csak annyi blokk, amely egy adott idő alatt érvényesíthető. Egy DAG-hálózatban a tranzakciók közvetlenül kapcsolódnak egymáshoz, nem pedig blokkokba csoportosítva, a tranzakciók másokkal egyidejűleg feldolgozhatók. Az eredmény a tranzakciós teljesítmény csökkent szűk keresztmetszete.