En Rettet Asyklisk Graf (DAG) er en type graf der det er umulig å komme tilbake til samme node ved å krysse kantene.

i grafteori er en graf en struktur bestående av noder som er forbundet med kanter. Du kan tenke på nodene som poeng og kantene som linjer trukket fra punkt til punkt.

‘Rettet’ betyr at kantene på grafen bare beveger seg i en retning, der fremtidige kanter er avhengige av tidligere. For eksempel, hvis du skulle grafere prosessen med matlaging og spise et måltid bestående av ris og kylling, må de involverte oppgavene være topologisk bestilt (eller topologisk sortert). Før du kan spise måltidet, må du forberede maten, så kanten vil nødvendigvis bli rettet fra forberedelse til å spise. Men før du kan tilberede maten, må du kjøpe ingrediensene, så igjen må kanten gå fra den tidligere hendelsen til den senere hendelsen. Forutsatt at risen ble kjøpt i en separat hendelse fra kyllingen, ville det være to separate kanter for dagligvarehandelen som ikke er koblet til hverandre, men som konvergerer ved tilberedning av maten.

‘Acyklisk’ betyr at Det er umulig å starte på et punkt i grafen og komme tilbake til det ved å følge kantene. Mens en syklus kommer tilbake til det opprinnelige utgangspunktet som en sirkel, fortsetter en asyklisk graf å bevege seg i lineær retning og sirkler aldri tilbake til utgangspunktet. For å fortsette med det tidligere eksempelet på kylling og rismiddag, kan du ikke bevege deg på grafen fra å kjøpe risen for å forberede maten til å kjøpe kyllingen, da det ville kreve å bevege seg bakover over grafen. Det er umulig å tilberede kyllingen hvis du ennå ikke har kjøpt den.DAGs Er probabilistiske grafiske representasjoner Av Bayesianske nettverk som tar sikte på å modellere betinget avhengighet (for eksempel å spise måltidet avhenger av å forberede det først). Flere cryptocurrencies bruker DAGs i stedet for blockchain datastrukturer for å behandle og validere transaksjoner. Med blockchains bygger alle noder i et nettverk på samme enkelt blockchain med hver blokk som refererer til den som kom før den. En mulig ulempe med denne strukturen er at den setter en grense på nettverkets transaksjonsgjennomstrømning, da det bare er så mange transaksjoner som kan passe inn i en enkelt blokk og bare så mange blokker som kan valideres i en gitt tid. I ET DAG-nettverk er transaksjoner direkte knyttet til hverandre i stedet for gruppert i blokker, og transaksjoner kan behandles samtidig med andre. Resultatet er en redusert flaskehals på transaksjonsgjennomstrømming.