een gerichte acyclische grafiek (DAG) is een type grafiek waarin het onmogelijk is om terug te komen naar dezelfde knoop door de randen te doorkruisen.

in de grafiektheorie is een grafiek een structuur die bestaat uit knooppunten die verbonden zijn door randen. Je kunt de knooppunten zien als punten en de randen als lijnen die van punt naar punt worden getrokken.

‘Directed’ betekent dat de randen van de grafiek slechts in één richting bewegen, waarbij toekomstige randen afhankelijk zijn van eerdere randen. Bijvoorbeeld, als je het proces van koken en het eten van een maaltijd bestaande uit rijst en kip grafisch, de betrokken taken zou moeten worden topologisch besteld (of topologisch gesorteerd). Voordat u de maaltijd kunt eten, moet u het voedsel bereiden, zodat de rand noodzakelijkerwijs van voorbereiding naar eten wordt gericht. Maar voordat je het eten kunt bereiden, moet je de ingrediënten kopen, dus opnieuw moet de rand van het eerdere evenement naar het latere evenement gaan. Stel dat de rijst werd gekocht in een aparte gebeurtenis van de kip, zouden er twee aparte randen voor de supermarkt winkelen evenementen die niet met elkaar zijn verbonden, maar die samenkomen bij het geval van het bereiden van het voedsel.

“acyclisch” betekent dat het onmogelijk is om op één punt van de grafiek te beginnen en erop terug te komen door de randen te volgen. Terwijl een cyclus terugkeert naar zijn oorspronkelijke beginpunt als een cirkel, gaat een acyclische grafiek verder in een lineaire richting en cirkelt nooit terug naar het beginpunt. Om verder te gaan met het eerdere voorbeeld van kip en rijst Diner, je kunt niet bewegen op de grafiek van het kopen van de rijst naar het bereiden van het voedsel naar het kopen van de kip, als dat zou vereisen achteruit bewegen over de grafiek. Het is onmogelijk om de kip te bereiden als je het nog niet hebt gekocht.

DAGs zijn probabilistische grafische representaties van Bayesiaanse netwerken die tot doel hebben voorwaardelijke afhankelijkheid te modelleren (bijvoorbeeld het eten van de maaltijd hangt af van het bereiden ervan).

verschillende cryptocurrencies gebruiken DAGs in plaats van blockchain datastructuren om transacties te verwerken en te valideren. Met blockchains, alle knooppunten in een netwerk bouwen op dezelfde enkele blockchain met elk blok verwijzen naar degene die ervoor kwam. Een mogelijk nadeel van deze structuur is dat het een limiet stelt aan de transactiedoorvoer van het netwerk, omdat er slechts zoveel transacties zijn die in een enkel blok passen en slechts zoveel blokken die in een bepaalde tijd kunnen worden gevalideerd. In een DAG-netwerk worden transacties direct aan elkaar gekoppeld in plaats van gegroepeerd in blokken, en transacties kunnen gelijktijdig met anderen worden verwerkt. Het resultaat is een kleiner knelpunt op transactiedoorvoer.