Directed acyclic graph

Definition

In mathematics, particularly graph theory, and computer science, a directed acyclic graph (DAG) is a directed graph with no directed cycles. That is, it consists of vertices and edges, with each edge directed from one vertex to another, such that following those directions will never form a closed loop. A directed graph is a DAG if and only if it can be topologically ordered, by arranging the vertices as a linear ordering that is consistent with all edge directions. DAGs have numerous scientific and computational applications, ranging from biology to information science to computation (scheduling).

Related concepts

Academic Press Acyclic dependencies principle Acyclic orientation Adjacency matrix Algorithm Alison Gopnik Arborescence (graph theory)Barabási–Albert model Bayesian network Bellman–Ford algorithm Bijective proof Binary decision diagram Bit Breadth-first search Brendan McKay (mathematician)Causal loop Causal sets Causality Charles E. Leiserson Chromatic polynomial Circular dependency Citation analysis Citation graph Citation impact Clifford Stein Closure problem Combinational logic Common subexpression elimination Compiler Computational complexity of matrix multiplication Computational geometry Computer science Computers and Intractability Condensation (graph theory)Consanguinity Covering relation Critical path method Cycle (graph theory)Cycle graph Data compression Data stream Data structure Dataflow programming David S. Johnson David Spiegelhalter Decision tree Delaunay triangulation Dense graph Dependency graph Depth-first search Derek J. de Solla Price Deterministic acyclic finite state automaton Dexter Kozen Dijkstra's algorithm Directed graph Distributed revision control Edge (graph theory)Edge contraction Eigenvalue Empty set Epidemiology Eric W. Weisstein Family tree Feedback arc set Feedback vertex set Feedforward neural network Frank Harary Frédérique Oggier George Furnas Git Gordon Royle Graph (discrete mathematics)Graph drawing Graph enumeration Graph theory Hasse diagram Herbert Wilf Identity matrix Influence diagram Instruction scheduling Introduction to Algorithms Journal of Integer Sequences Journal of the American Society for Information Science Judea Pearl Judgment (law)János Pach Laura Schulz Linear extension Linear time Logic gate Logical matrix Longest path problem Loop (graph theory)M. Lothaire Main path analysis Makefile Management Science (journal)MathWorld Mathematics Matrilineal Maximum flow problem Micha Sharir Michael Garey Milestone (project management)Moral graph Multitree NP-hard Neil Sloane Network Science Nicos Christofides Object file On-Line Encyclopedia of Integer Sequences Orientation (graph theory)Parallel algorithm Partial order Path (graph theory)Patrilineal Pedigree collapse Philip Dawid Ping Zhang (graph theorist)Point location Polytree Postorder Price's model Prior art Program evaluation and review technique Ptolemaic dynasty Randomization Randomized algorithm Reachability Real number Recurrence relation Richard P. Stanley Robert Sedgewick (computer scientist)Ron Rivest Schedule Scheduling (computing)Science (journal)Shortest path Source code Spreadsheet Steffen Lauritzen String (computer science)Strongly connected component Thomas H. Cormen Topological ordering Topological sorting Total order Transitive closure Transitive reduction Tree (graph theory)Trie Truth assignment Vertex (graph theory)W. H. Freeman and Company Walk (graph theory)

18 concepts already in your glossary