en rettet acyklisk graf (DAG) er en type graf, hvor det er umuligt at komme tilbage til den samme knude ved at krydse kanterne.

i grafteori er en graf en struktur bestående af noder, der er forbundet med kanter. Du kan tænke på knudepunkterne som punkter og kanterne som linjer trukket fra punkt til punkt.

‘rettet’ betyder, at grafens kanter kun bevæger sig i en retning, hvor fremtidige kanter er afhængige af tidligere. For eksempel, hvis du skulle tegne processen med madlavning og spise et måltid bestående af ris og kylling, skulle de involverede opgaver være topologisk bestilt (eller topologisk sorteret). Før du kan spise måltidet, skal du forberede maden, så kanten nødvendigvis vil blive rettet fra forberedelse frem til at spise. Men før du kan tilberede maden, skal du købe ingredienserne, så igen skal kanten gå fra den tidligere begivenhed til den senere begivenhed. Hvis man antager, at risen blev købt i en separat begivenhed fra kyllingen, ville der være to separate kanter til købmandshændelserne, der ikke er forbundet med hinanden, men som konvergerer ved tilberedning af maden.

‘acyklisk’ betyder, at det er umuligt at starte på et punkt i grafen og komme tilbage til den ved at følge kanterne. Mens en cyklus kommer tilbage til det oprindelige udgangspunkt som en cirkel, fortsætter en acyklisk graf i en lineær retning og cirkler aldrig tilbage til startpunktet. For at fortsætte med det tidligere eksempel på kylling-og rismiddag kan du ikke flytte på grafen fra at købe risen til at forberede maden til at købe kyllingen, da det ville kræve at flytte baglæns over grafen. Det er umuligt at tilberede kyllingen, hvis du endnu ikke har købt den.

dag ‘ er er sandsynlige grafiske repræsentationer af bayesiske netværk, der sigter mod at modellere betinget afhængighed (f.eks.

flere cryptocurrencies bruger dag ‘ er snarere end blockchain-datastrukturer for at behandle og validere transaktioner. Med blockchains bygger alle knudepunkter i et netværk på den samme enkelt blockchain, hvor hver blok refererer til den, der kom før den. En mulig ulempe ved denne struktur er, at den sætter en grænse for netværkets transaktionsgennemgang, da der kun er så mange transaktioner, der kan passe i en enkelt blok og kun så mange blokke, der kan valideres på et givet tidspunkt. I et DAG-netværk er transaktioner direkte knyttet til hinanden i stedet for grupperet i blokke, og transaktioner kan behandles samtidigt med andre. Resultatet er en mindsket flaskehals på transaktionsgennemstrømning.