Directed acyclic graph
In mathematics, particularly graph theory, and computer science, a directed acyclic graph (DAG) is a directed graph with no directed cycles.
≈ 6 min read
Names in other languages
No names in other languages are held for this entry yet.
Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.
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. 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 (v_1,v_2,\dotsc) of vertices such that each consecutive pair (v_i,v_{i+1}) is connected by a directed edge. A path is a walk where all vertices are distinct. A cycle is a walk (v_1,v_2,\dotsc,v_n) where the only repeated vertex is v_n=v_1 , meaning the last vertex equals the first vertex.
A directed acyclic graph is a directed graph that has no cycles. representing the partial order of set inclusion (⊆) among the subsets of a three-element set|alt=Refer to caption 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. a_n = \sum_{k=1}^n (-1)^{k-1} {n\choose k}2^{k(n-k)} a_{n-k}.
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. of the blue directed graph. It is formed by contracting each strongly connected component of the blue graph into a single yellow vertex.|alt=Refer to caption 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. 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. , with many marriages between close relatives causing pedigree collapse|alt=Refer to caption Family trees may be seen as directed acyclic graphs, with a vertex for each family member and an edge for each parent-child relationship. Despite the name, these graphs are not necessarily trees because of the possibility of marriages between relatives (so a child has a common ancestor on both the mother's and father's side) causing pedigree collapse.
The graphs of matrilineal descent (mother-daughter relationships) and patrilineal descent (father-son relationships) are trees within this graph. Because no one can become their own ancestor, family trees are acyclic.
The version history of a distributed revision control system, such as Git, generally has the structure of a directed acyclic graph, in which there is a vertex for each revision and an edge connecting pairs of revisions that were directly derived from each other. These are not trees in general due to merges.
In many randomized algorithms in computational geometry, the algorithm maintains a history DAG representing the version history of a geometric structure over the course of a sequence of changes to the structure. For instance in a randomized incremental algorithm for Delaunay triangulation, the triangulation changes by replacing one triangle by three smaller triangles when each point is added, and by "flip" operations that replace pairs of triangles by a different pair of triangles.
The history DAG for this algorithm has a vertex for each triangle constructed as part of the algorithm, and edges from each triangle to the two or three other triangles that replace it. This structure allows point location queries to be answered efficiently: to find the location of a query point in the Delaunay triangulation, follow a path in the history DAG, at each step moving to the replacement triangle that contains .
The final triangle reached in this path must be the Delaunay triangle that contains .
Text derived from https://en.wikipedia.org/w/index.php?oldid=1378707204 under CC BY-SA 4.0; modifications have been made.