mini|stående|Exempel på en riktad acyklisk graf. Riktad acyklisk graf eller acyklisk digraf (ibland DAG, av ), är inom matematik, särskilt grafteori och datavetenskap, en riktad graf utan cykler. Det vill säga, den består av hörn och kanter (även kallade bågar), där varje kant är riktad från ett hörn till ett annat, så att det aldrig kommer att bildas en sluten slinga att följa dessa riktningar. En riktad graf är acyklisk endast om den kan ordnas topologiskt genom att arrangera noderna i en linjär ordning som är förenlig med alla kantriktningar.
Acyklisk digrafer har många vetenskapliga och beräkningsmässiga tillämpningar, allt från biologi (evolution, släktträd, epidemiologi) till informationsvetenskap (citeringsnätverk) och beräkning (schemaläggning).
Källor
Webbkällor
Kategori:Grafteori