Directed Acyclic Graph

In mathematics and computer science, a directed acyclic graph (DAG), is a finite directed graph with no directed cycles. wikipedia

That is, it consists of finitely many vertices and edges, with each edge directed from one vertex to another, such that there is no way to start at any vertex v and follow a consistently-directed sequence of edges that eventually loops back to v again. Equivalently, a DAG is a directed graph that has a topological ordering, a sequence of the vertices such that every edge is directed from earlier to later in the sequence.

Yes, that is correct. A DAG is a finite directed graph that has no directed cycles. This means that there is a unique path between any two vertices in the graph and there is a topological ordering of the vertices, which means that the vertices can be arranged in a linear order such that all edges in the graph go from an earlier vertex to a later vertex in the order. This property makes DAGs useful in various applications such as scheduling, data flow analysis, and Bayesian networks. Additionally, many algorithms, such as topological sorting, can be performed efficiently on DAGs because of their specific structure.

DAGs may be used to model many different kinds of information. The reachability relation in a DAG forms a partial order, and any finite partial order may be represented by a DAG using reachability.

The program evaluation and review technique uses DAGs to model the milestones and activities of large human projects, and schedule these projects to use as little total time as possible.

Scheduling of computer operations such as the updates to a spreadsheet or the compilation operations in a makefile can also be performed using topological orderings of DAGs.

Combinational logic blocks in electronic circuit design, and the operations in dataflow programming languages, involve acyclic networks of processing elements.

DAGs can also represent collections of events and their influence on each other, either in a probabilistic structure such as a Bayesian network or as a record of historical data such as family trees or the version histories of distributed revision control systems.

DAGs can also be used as a compact representation of sequence data, such as the directed acyclic word graph representation of a collection of strings, or the binary decision diagram representation of sequences of binary choices.

Important polynomial time computational problems on DAGs include topological sorting (finding a topological ordering), construction of the transitive closure and transitive reduction (the largest and smallest DAGs with the same reachability relation, respectively), and the closure problem, in which the goal is to find a minimum-weight subset of vertices with no edges connecting them to the rest of the graph. Transforming a directed graph with cycles into a DAG by deleting as few vertices or edges as possible (the feedback vertex set and feedback edge set problem, respectively) is NP-hard, but any directed graph can be made into a DAG (its condensation) by contracting each strongly connected component into a single supervertex. The problems of finding shortest paths and longest paths can be solved on DAGs in linear time, in contrast to arbitrary graphs for which shortest path algorithms are slower and longest path problems are NP-hard.

The corresponding concept for undirected graphs is a forest, an undirected graph without cycles. Choosing an orientation for a forest produces a special kind of directed acyclic graph called a polytree. However there are many other kinds of directed acyclic graph that are not formed by orienting the edges of an undirected acyclic graph. Moreover, every undirected graph has an acyclic orientation, an assignment of a direction for its edges that makes it into a directed acyclic graph. To emphasize that DAGs are not the same thing as directed versions of undirected acyclic graphs, some authors call them acyclic directed graphs or acyclic digraphs.