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 (also called arcs), 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 (evolution, family trees, epidemiology) to information science (citation networks) to computation (scheduling).
Directed acyclic graphs are also called acyclic directed graphs or acyclic digraphs.
Definitions A graph is formed by vertices and by edges connecting pairs of vertices, where the vertices can be any kind of object that is connected in pairs by edges. In the case of a directed graph, each edge has an orientation, from one vertex to another vertex. A walk in a directed graph is a (finite or infinite) sequence of vertices such that each consecutive pair is connected by a directed edge. A path is a walk where all vertices are distinct. A cycle is a walk where the only repeated vertex is , meaning the last vertex equals the first vertex. A directed acyclic graph is a directed graph that has no cycles....
Mathematical properties Reachability relation, transitive closure, and transitive reduction
The reachability relation of a DAG can be formalized as a partial order on the vertices of the DAG. In this partial order, two vertices and are ordered as exactly when there exists a directed path from to in the DAG; that is, when can reach (or is reachable from ).. However, different DAGs may give rise to the same reachability relation and the same partial order.. For example, a DAG with two edges and has the same reachability relation as the DAG with three edges , , and . Both of these DAGs produce the same partial order, in which the vertices are ordered as .
The transitive closure of a DAG is the graph with the most edges that has the same reachability relation as the DAG. It has an edge for every pair of vertices (, ) in the reachability relation of the DAG, and may therefore be thought of as a direct translation of the reachability relation into graph-theoretic terms. The same method of translating partial orders into DAGs works more generally: for every finite partially ordered set , the graph that has a vertex for every element of and an edge for every pair of elements in is automatically a transitively closed DAG, and has as its reachability relation. In this way, every finite partially ordered set can be represented as a DAG.
The transitive reduction of a DAG is the graph with the fewest edges that has the same reachability relation as the DAG. It has an edge for every pair of vertices (, ) in the covering relation of the reachability relation of the DAG. It is a subgraph of the DAG, formed by discarding the edges for which the DAG also contains a longer directed path from to . Like the transitive closure, the transitive reduction is uniquely defined for DAGs. In contrast, for a directed graph that is not acyclic, there can be more than one minimal subgraph with the same reachability relation.. Transitive reductions are useful in visualizing the partial orders they represent, because they have fewer edges than other graphs representing the same orders and therefore lead to simpler graph drawings. A Hasse diagram of a partial order is a drawing of the transitive reduction in which the orientation of every edge is shown by placing the starting vertex of the edge in a lower position than its ending vertex..
Topological ordering
A topological ordering of a directed graph is an ordering of its vertices into a sequence, such that for every edge the start vertex of the edge occurs earlier in the sequence than the ending vertex of the edge. A graph that has a topological ordering cannot have any cycles, because the edge into the earliest vertex of a cycle would have to be oriented the wrong way. Therefore, every graph with a topological ordering is acyclic. Conversely, every directed acyclic graph has at least one topological ordering. The existence of a topological ordering can therefore be used as an equivalent definition of a directed acyclic graphs: they are exactly the graphs that have topological orderings. In general, this ordering is not unique; a DAG has a unique topological ordering if and only if it has a directed path containing all the vertices, in which case the ordering is the same as the order in which the vertices appear in the path..
The family of topological orderings of a DAG is the same as the family of linear extensions of the reachability relation for the DAG,. so any two graphs representing the same partial order have the same set of topological orders.
Convex hull A set X of vertices of an acyclic digraph D is convex if X≠∅ and there is no directed path between vertices of X which contains a vertex not in X. Expressed differently, a set X of vertices is convex if for every pair of vertices , ∈ X, every directed path from to is entirely contained within X.
The convex hull of a subset of vertices S is the smallest convex set containing S. That is, the convex hull of a set S in a DAG consists of all vertices that lie on any directed path between two vertices in S. It can be computed as the intersection of the set of all vertices that are reachable from any vertex in S (including S itself) and the set of all vertices that can reach any vertex in S (including S itself).
Combinatorial enumeration The graph enumeration problem of counting directed acyclic graphs was studied by .. See also . The number of DAGs on labeled vertices, for (without restrictions on the order in which these numbers appear in a topological ordering of the DAG) is 1, 1, 3, 25, 543, 29281, 3781503, … . These numbers may be computed by the recurrence relation
Eric W. Weisstein conjectured, and proved, that the same numbers count the (0,1) matrices for which all eigenvalues are positive real numbers. The proof is bijective: a matrix is an adjacency matrix of a DAG if and only if is a (0,1) matrix with all eigenvalues positive, where denotes the identity matrix. Because a DAG cannot have self-loops, its adjacency matrix must have a zero diagonal, so adding preserves the property that all matrix coefficients are 0 or 1., Article 04.3.3.
Related families of graphs
A multitree (also called a strongly unambiguous graph or a mangrove) is a DAG in which there is at most one directed path between any two vertices. Equivalently, it is a DAG in which the subgraph reachable from any vertex induces an undirected tree..
A polytree (also called a directed tree) is a multitree formed by orienting the edges of an undirected tree..
An arborescence is a polytree formed by orienting the edges of an undirected tree away from a particular vertex, called the root of the arborescence.
Computational problems Topological sorting and recognition
Topological sorting is the algorithmic problem of finding a topological ordering of a given DAG. It can be solved in linear time. Section 22.4, Topological sort, pp. 549–552. Kahn's algorithm for topological sorting builds the vertex ordering directly. It maintains a list of vertices that have no incoming edges from other vertices that have not already been included in the partially constructed topological ordering; initially this list consists of the vertices with no incoming edges at all. Then, it repeatedly adds one vertex from this list to the end of the partially constructed topological ordering, and checks whether its neighbors should be added to the list. The algorithm terminates when all vertices have been processed in this way. Alternatively, a topological ordering may be constructed by reversing a postorder numbering of a depth-first search graph traversal.
It is also possible to check whether a given directed graph is a DAG in linear time, either by attempting to find a topological ordering and then testing for each edge whether the resulting ordering is validFor depth-first search based topological sorting algorithm, this validity check can be interleaved with the topological sorting algorithm itself; see e.g. . or alternatively, for some topological sorting algorithms, by verifying that the algorithm successfully orders all the vertices without meeting an error condition., pp. 50–51.
Construction from cyclic graphs Any undirected graph may be made into a DAG by choosing a total order for its vertices and directing every edge from the earlier endpoint in the order to the later endpoint. The resulting orientation of the edges is called an acyclic orientation. Different total orders may lead to the same acyclic orientation, so an -vertex graph can have fewer than acyclic orientations. The number of acyclic orientations is equal to , where is the chromatic polynomial of the given graph..
Any directed graph may be made into a DAG by removing a feedback vertex set or a feedback arc set, a set of vertices or edges (respectively) that touches all cycles. However, the smallest such set is NP-hard to find., Problems GT7 and GT8, pp. 191–192. An arbitrary directed graph may also be transformed into a DAG, called its condensation, by contracting each of its strongly connected components into a single supervertex.. When the graph is already acyclic, its smallest feedback vertex sets and feedback arc sets are empty, and its condensation is the graph itself.
Transitive closure and transitive reduction The transitive closure of a given DAG, with vertices and edges, may be constructed in time by using either breadth-first search or depth-first search to test reachability from each vertex., p. 495. Alternatively, it can be solved in time where is the exponent for matrix multiplication algorithms; this is a theoretical improvement over the bound for dense graphs., p. 496.
In all of these transitive closure algorithms, it is possible to distinguish pairs of vertices that are reachable by at least one path of length two or more from pairs that can only be connected by a length-one path. The transitive reduction consists of the edges that form length-one paths that are the only paths connecting their endpoints. Therefore, the transitive reduction can be constructed in the same asymptotic time bounds as the transitive closure., p. 38.
Closure problem
The closure problem takes as input a vertex-weighted directed acyclic graph and seeks the minimum (or maximum) weight of a closure – a set of vertices C, such that no edges leave C. The problem may be formulated for directed graphs without the assumption of acyclicity, but with no greater generality, because in this case it is equivalent to the same problem on the condensation of the graph. It may be solved in polynomial time using a reduction to the maximum flow problem..
Path algorithms Some algorithms become simpler when used on DAGs instead of general graphs, based on the principle of topological ordering. For example, it is possible to find shortest paths and longest paths from a given starting vertex in DAGs in linear time by processing the vertices in a topological order, and calculating the path length for each vertex to be the minimum or maximum length obtained via any of its incoming edges.Cormen et al. 2001, Section 24.2, Single-source shortest paths in directed acyclic graphs, pp. 592–595. In contrast, for arbitrary graphs the shortest path may require slower algorithms such as Dijkstra's algorithm or the Bellman–Ford algorithm,Cormen et al. 2001, Sections 24.1, The Bellman–Ford algorithm, pp. 588–592, and 24.3, Dijkstra's algorithm, pp. 595–601. and longest paths in arbitrary graphs are NP-hard to find.Cormen et al. 2001, p. 966.
Applications Scheduling