1,569
个编辑
更改
跳到导航
跳到搜索
Moved page from wikipedia:en:Directed acyclic graph (history)
此词条暂由彩云小译翻译，翻译字数共4005，未经人工整理和审校，带来阅读不便，请见谅。
{{short description|Directed graph with no directed cycles}}
{{good article}}
[[File:Tred-G.svg|thumb|Example of a directed acyclic graph.]]
Example of a directed acyclic graph.
有向无环图的例子。
In [[mathematics]], particularly [[graph theory]], and [[computer science]], a '''directed acyclic graph''' ('''DAG''' or '''dag''' {{IPAc-en|audio=en-us-DAG.ogg|ˈ|d|æ|g}}) is a [[directed graph]] with no [[Cycle graph#Directed cycle graph|directed cycles]]. That is, it consists of [[Vertex (graph theory)|vertices]] and [[edge (graph theory)|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 [[topological ordering|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 sociology (citation networks) to computation (scheduling).
In mathematics, particularly graph theory, and computer science, a directed acyclic graph (DAG or 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 sociology (citation networks) to computation (scheduling).
在数学，特别是图论和计算机科学中，有向无环图图(DAG 或 DAG)是一个没有有向圈的有向图。也就是说，它由顶点和边(也称为弧)组成，每条边都从一个顶点指向另一个顶点，这样沿着这些方向走永远不会形成一个闭合的循环。有向图是一个有向无环图当且仅当它可以通过将顶点按照与所有边方向一致的线性顺序排列而拓扑排序。DAGs 有许多科学和计算应用，从生物学(进化论，家族树，流行病学)到社会学(引文网络)到计算(调度)。
==Definitions==
A [[Graph (discrete mathematics)|graph]] is formed by [[vertex (graph theory)|vertices]] and by [[edge (graph theory)|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 [[Path (graph theory)|path]] in a directed graph is a sequence of edges having the property that the ending vertex of each edge in the sequence is the same as the starting vertex of the next edge in the sequence; a path forms a cycle if the starting vertex of its first edge equals the ending vertex of its last edge. A directed acyclic graph is a directed graph that has no cycles.<ref name="thul">{{citation|title=Graphs: Theory and Algorithms|first1=K.|last1=Thulasiraman|first2=M. N. S.|last2=Swamy|publisher=John Wiley and Son|year=1992|isbn=978-0-471-51356-8|contribution=5.7 Acyclic Directed Graphs|page=118}}.</ref><ref name="bang">{{citation|title=Digraphs: Theory, Algorithms and Applications|first1=Jørgen|last1=Bang-Jensen|series=Springer Monographs in Mathematics|edition=2nd|publisher=Springer-Verlag|year=2008|isbn=978-1-84800-997-4|contribution=2.1 Acyclic Digraphs|pages=32–34}}.</ref><ref>{{citation|title=Graph theory: an algorithmic approach|first=Nicos|last=Christofides|author-link=Nicos Christofides|publisher=Academic Press|year=1975|pages=170–174}}.</ref>
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 path in a directed graph is a sequence of edges having the property that the ending vertex of each edge in the sequence is the same as the starting vertex of the next edge in the sequence; a path forms a cycle if the starting vertex of its first edge equals the ending vertex of its last edge. A directed acyclic graph is a directed graph that has no cycles.
图是由顶点和连接顶点对的边组成的，顶点可以是任何一种由边成对连接的对象。在有向图的情况下，每条边都有一个方向，从一个顶点到另一个顶点。有向图中的路是一个边序列，它具有序列中每条边的结束顶点与序列中下一条边的起始顶点相同的性质; 如果一条路的第一条边的起始顶点与它的最后一条边的结束顶点相等，那么它就形成了一个圈。有向无环图是一个没有圈的有向图。
A vertex {{mvar|v}} of a directed graph is said to be [[Reachability|reachable]] from another vertex {{mvar|u}} when there exists a path that starts at {{mvar|u}} and ends at {{mvar|v}}. As a special case, every vertex is considered to be reachable from itself (by a path with zero edges). If a vertex can reach itself via a nontrivial path (a path with one or more edges), then that path is a cycle, so another way to define directed acyclic graphs is that they are the graphs in which no vertex can reach itself via a nontrivial path.<ref>{{citation|title=Simulation Techniques for Discrete Event Systems|volume=14|series=Cambridge Computer Science Texts|first=I.|last=Mitrani|year=1982|publisher=Cambridge University Press|isbn=9780521282826|page=27|url=https://books.google.com/books?id=CF04AAAAIAAJ&pg=PA27}}.</ref>
A vertex of a directed graph is said to be reachable from another vertex when there exists a path that starts at and ends at . As a special case, every vertex is considered to be reachable from itself (by a path with zero edges). If a vertex can reach itself via a nontrivial path (a path with one or more edges), then that path is a cycle, so another way to define directed acyclic graphs is that they are the graphs in which no vertex can reach itself via a nontrivial path.
有向图的一个顶点称为从另一个顶点到达的，当存在一条从点开始到点结束的路时。作为一种特殊情况，每个顶点都被认为是从它自身可到达的(通过一条零边的路径)。如果一个顶点可以通过一条非平凡的路(一条有一条或多条边的路)到达它自己，那么这条路就是一个圈，因此定义有向无圈图的另一种方法是，它们是图中没有顶点可以通过一条非平凡的路到达它自己。
== Mathematical properties ==
=== Reachability, transitive closure, and transitive reduction ===
{{multiple image|image1=Tred-G.svg|width1=175|image2=Tred-Gprime.svg|width2=124|caption1=A DAG {{mvar|G}}|caption2=Transitive reduction of {{mvar|G}}}}
The [[reachability]] relationship in any directed acyclic graph can be formalized as a [[partial order]] {{math|≤}} on the vertices of the DAG. In this partial order, two vertices {{mvar|u}} and {{mvar|v}} are ordered as {{math|''u'' ≤ ''v''}} exactly when there exists a directed path from {{mvar|u}} to {{mvar|v}} in the DAG; that is, when {{mvar|v}} is reachable from {{mvar|u}}.<ref>{{citation|title=The Design and Analysis of Algorithms|series=Monographs in Computer Science|first=Dexter|last=Kozen|author-link=Dexter Kozen|publisher=Springer|year=1992|isbn=978-0-387-97687-7|page=9|url=https://books.google.com/books?id=L_AMnf9UF9QC&pg=PA9}}.</ref> However, different DAGs may give rise to the same reachability relation and the same partial order.<ref>{{citation|title=Loop Transformations for Restructuring Compilers: The Foundations|first=Utpal|last=Banerjee|publisher=Springer|year=1993|isbn=978-0-7923-9318-4|page=19|contribution=Exercise 2(c)|url=https://books.google.com/books?id=Cog7zSSlqFwC&pg=PA19}}.</ref> For example, the DAG with two edges {{math|''a'' → ''b''}} and {{math|''b'' → ''c''}} has the same reachability relation as the graph with three edges {{math|''a'' → ''b''}}, {{math|''b'' → ''c''}}, and {{math|''a'' → ''c''}}. Both of these DAGS produce the same partial order, in which the vertices are ordered as {{math|''a'' ≤ ''b'' ≤ ''c''}}.
The reachability relationship in any directed acyclic graph 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 is reachable from . However, different DAGs may give rise to the same reachability relation and the same partial order. For example, the DAG with two edges and has the same reachability relation as the graph with three edges , , and . Both of these DAGS produce the same partial order, in which the vertices are ordered as .
任何有向无环图中的可达关系都可以形式化为 DAG 顶点上的一个偏序。在这个部分顺序中，两个顶点的顺序与有向无环图中存在从到的有向路径时的顺序完全一致; 也就是说，当从。然而，不同的 DAGs 可能产生相同的可达关系和相同的偏序。例如，有向无环图具有两条边，并且与具有三条边、和的图具有相同的可达性关系。这两种 DAGS 产生相同的偏序，其中顶点的顺序为。
[[File:Hasse diagram of powerset of 3.svg|thumb|300px|A [[Hasse diagram]] representing the partial order of set inclusion (⊆) among the subsets of a three-element set.]]
A [[Hasse diagram representing the partial order of set inclusion (⊆) among the subsets of a three-element set.]]
[[ Hasse 图表示三元素集合子集中集合包含(something)的偏序]]
If {{mvar|G}} is a DAG, its [[transitive closure]] is the graph with the most edges that represents the same reachability relation. It has an edge {{math|''u'' → ''v''}} whenever {{mvar|u}} can reach {{mvar|v}}. That is, it has an edge for every related pair {{math|''u'' ≤ ''v''}} of distinct elements in the reachability relation of {{mvar|G}}, and may therefore be thought of as a direct translation of the reachability relation {{math|≤}} into graph-theoretic terms. The same method of translating partial orders into DAGs works more generally: for every finite partially ordered set {{math|(''S'', ≤)}}, the graph that has a vertex for each member of {{mvar|S}} and an edge for each pair of elements related by {{math|''u'' ≤ ''v''}} is automatically a transitively closed DAG, and has {{math|(''S'', ≤)}} as its reachability relation. In this way, every finite partially ordered set can be represented as the reachability relation of a DAG.
If is a DAG, its transitive closure is the graph with the most edges that represents the same reachability relation. It has an edge whenever can reach . That is, it has an edge for every related pair of distinct elements in the reachability relation of , 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 each member of and an edge for each pair of elements related by is automatically a transitively closed DAG, and has as its reachability relation. In this way, every finite partially ordered set can be represented as the reachability relation of a DAG.
如果是一个有向无环图，那么它的有向无环传递闭包图就是具有最多边的图，这些边表示相同的可达性关系。它有一个优势，无论何时可以达到。也就是说，可达关系中每一对相关的不同元素都有一个边，因此可以认为是可达关系直接转化为图论术语。同样的将偏序转换为 DAGs 的方法更为普遍: 对于每个有限偏序集，每个成员有一个顶点，每对相关元素有一条边的图是自动传递闭的 DAG，并且具有可达关系。这样，每个有限偏序集都可以表示为一个 DAG 的可达关系。
The [[transitive reduction]] of a DAG {{mvar|G}} is the graph with the fewest edges that represents the same reachability relation as {{mvar|G}}. It is a subgraph of {{mvar|G}}, formed by discarding the edges {{math|''u'' → ''v''}} for which {{mvar|G}} also contains a longer path connecting the same two vertices.
The transitive reduction of a DAG is the graph with the fewest edges that represents the same reachability relation as . It is a subgraph of , formed by discarding the edges for which also contains a longer path connecting the same two vertices.
有向无环图的传递约简是一个具有最少边的图，它表示的可达性关系与。这是一个子图的，由丢弃的边，其中也包含一个较长的路径连接相同的两个顶点。
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.<ref>{{citation|title=Digraphs: Theory, Algorithms and Applications|series=Springer Monographs in Mathematics|first1=Jørgen|last1=Bang-Jensen|first2=Gregory Z.|last2=Gutin|publisher=Springer|year=2008|isbn=978-1-84800-998-1|url=https://books.google.com/books?id=4UY-ucucWucC&pg=PA36|contribution=2.3 Transitive Digraphs, Transitive Closures and Reductions|pages=36–39}}.</ref>
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.
和传递闭包一样，传递约简也是针对 DAGs 的唯一定义。相反，对于不是无圈的有向图，可以有多个具有相同可达关系的极小子图。
If a DAG {{mvar|G}} has a reachability relation described by the partial order {{math|≤}}, then the transitive reduction of {{mvar|G}} is a subgraph of {{mvar|G}} that has an edge {{math|''u'' → ''v''}} for every pair in the [[covering relation]] of {{math|≤}}. 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 drawing]]s. A [[Hasse diagram]] of a partial order is a drawing of the transitive reduction in which the orientation of each edge is shown by placing the starting vertex of the edge in a lower position than its ending vertex.<ref>{{citation|title=Graphs, Networks and Algorithms|volume=5|series=Algorithms and Computation in Mathematics|first=Dieter|last=Jungnickel|publisher=Springer|year=2012|isbn=978-3-642-32278-5|pages=92–93|url=https://books.google.com/books?id=PrXxFHmchwcC&pg=PA92}}.</ref>
If a DAG has a reachability relation described by the partial order , then the transitive reduction of is a subgraph of that has an edge for every pair in the covering relation of . 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 each edge is shown by placing the starting vertex of the edge in a lower position than its ending vertex.
如果一个有向无环图具有一个由偏序描述的可达关系，那么它的传递约简就是一个子图，该子图的覆盖关系中的每一对都有一个边。传递约简在可视化它们所表示的部分顺序方面很有用，因为它们比其他表示相同顺序的图有更少的边，从而导致更简单的图绘制。偏序哈斯图是一幅传递归约图，其中每条边的方向通过将边的起始顶点放置在比其终止顶点位置更低的位置来显示。
=== Topological ordering ===
{{multiple image|image1=Topological Ordering.svg|caption1=A [[Topological sorting|topological ordering]] of a directed acyclic graph: every [[Edge (graph theory)|edge]] goes from earlier in the ordering (upper left) to later in the ordering (lower right). A directed graph is acyclic if and only if it has a topological ordering.|image2=Transitive Closure.svg|caption2=Adding the red edges to the blue directed acyclic graph produces another DAG, the [[transitive closure]] of the blue graph. For each red or blue edge {{mvar|uv}}, {{mvar|v}} is [[Reachability|reachable]] from {{mvar|u}}: there exists a blue path starting at {{mvar|u}} and ending at {{mvar|v}}.}}
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.<ref name="bang"/>
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.<ref>{{citation|title=Algorithms|first1=Robert|last1=Sedgewick|author1-link=Robert Sedgewick (computer scientist)|first2=Kevin|last2=Wayne|edition=4th|publisher=Addison-Wesley|year=2011|isbn=978-0-13-276256-4|url=https://books.google.com/books?id=idUdqdDXqnAC&pg=PA598|pages=598–599|contribution=4,2,25 Unique topological ordering}}.</ref>
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.
有向无环图的拓扑序族与有向无环图的可达关系的线性扩张族相同，因此任意两个表示相同偏序的图具有相同的拓扑序集。
The family of topological orderings of a DAG is the same as the family of [[linear extension]]s of the reachability relation for the DAG,<ref>{{citation|title=A Short Course in Discrete Mathematics|series=Dover Books on Computer Science|first1=Edward A.|last1=Bender|first2=S. Gill|last2=Williamson|publisher=Courier Dover Publications|year=2005|isbn=978-0-486-43946-4|page=142|url=https://books.google.com/books?id=iuEoAwAAQBAJ&pg=PA142|contribution=Example 26 (Linear extensions – topological sorts)}}.</ref> so any two graphs representing the same partial order have the same set of topological orders.
=== Combinatorial enumeration ===
The graph enumeration problem of counting directed acyclic graphs was studied by .
研究了计数有向无圈图的图计数问题。
The [[graph enumeration]] problem of counting directed acyclic graphs was studied by {{harvtxt|Robinson|1973}}.<ref name="enum">{{citation|first=R. W.|last=Robinson|contribution=Counting labeled acyclic digraphs|pages=239–273|editor-first=F.|editor-last=Harary|editor-link=Frank Harary|title=New Directions in the Theory of Graphs|publisher=Academic Press|year=1973}}. See also {{citation
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
在有标记的顶点上的 DAGs 数量为(对这些数字在有向无环图的拓扑顺序中出现的顺序没有限制)
|last1 = Harary | first1 = Frank | author1-link = Frank Harary | first2 = Edgar M. | last2 = Palmer | year = 1973| title = Graphical Enumeration | publisher = [[Academic Press]] | isbn = 978-0-12-324245-7 | page=19}}.</ref>
1, 1, 3, 25, 543, 29281, 3781503, … .
1, 1, 3, 25, 543, 29281, 3781503, … .
The number of DAGs on {{mvar|n}} labeled vertices, for {{math|1=''n'' = 0, 1, 2, 3, …}} (without restrictions on the order in which these numbers appear in a topological ordering of the DAG) is
These numbers may be computed by the recurrence relation
这些数字可能是由美国递回关系式计算出来的
:1, 1, 3, 25, 543, 29281, 3781503, … {{OEIS|id=A003024}}.
<math>a_n = \sum_{k=1}^n (-1)^{k-1} {n\choose k}2^{k(n-k)} a_{n-k}.</math> 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.
< math > a _ n = sum _ { k = 1} ^ n (- 1) ^ { k-1}{ n choose k }2 ^ { k (n-k)} a { n-k }.证明了同一个数可以计算所有特征值为正实数的(0,1)矩阵。证明是双射的: 一个矩阵是一个 DAG 的邻接矩阵当且仅当它是一个所有特征值为正的矩阵，其中表示单位矩阵。因为一个 DAG 不能有自循环，所以它的邻接矩阵必须有一个零对角线，所以加上这一点保留了所有矩阵系数都是0或1的性质。
These numbers may be computed by the [[recurrence relation]]
:<math>a_n = \sum_{k=1}^n (-1)^{k-1} {n\choose k}2^{k(n-k)} a_{n-k}.</math><ref name="enum" />
[[Eric W. Weisstein]] conjectured,<ref>{{MathWorld | urlname=WeissteinsConjecture | title=Weisstein's Conjecture|mode=cs2}}</ref> and {{harvtxt|McKay|Royle|Wanless|Oggier|2004}} proved, that the same numbers count the [[Logical matrix|(0,1) matrices]] for which all [[eigenvalue]]s are positive [[real number]]s. The proof is [[bijective proof|bijective]]: a matrix {{mvar|A}} is an [[adjacency matrix]] of a DAG if and only if {{math|''A'' + ''I''}} is a (0,1) matrix with all eigenvalues positive, where {{mvar|I}} denotes the [[identity matrix]]. Because a DAG cannot have [[Loop (graph theory)|self-loops]], its adjacency matrix must have a zero diagonal, so adding {{mvar|I}} preserves the property that all matrix coefficients are 0 or 1.<ref>{{citation|last1=McKay|first1=B. D.|author1-link=Brendan McKay|last2=Royle|first2=G. F.|author2-link=Gordon Royle|last3=Wanless|first3=I. M.|last4=Oggier|first4=F. E.|author4-link= Frédérique Oggier |last5=Sloane|first5=N. J. A.|author5-link= Neil Sloane|last6=Wilf|first6=H.|author6-link=Herbert Wilf|title=Acyclic digraphs and eigenvalues of (0,1)-matrices|journal=[[Journal of Integer Sequences]]|volume=7|year=2004|url=http://www.cs.uwaterloo.ca/journals/JIS/VOL7/Sloane/sloane15.html}}, Article 04.3.3.</ref>
{{multiple image
{多重图像
|image1=Polytree.svg|caption1=A polytree, a DAG formed by orienting the edges of an undirected tree
1 = Polytree.svg | caption1 = 一个多边形树，一个有向无向树的边缘定向形成的 DAG
=== Related families of graphs ===
|image2=Butterfly multitree.svg|caption2=A multitree, A DAG in which each subgraph reachable from a single vertex (red) is a tree
| image2 = Butterfly multitree.svg | caption2 = 一个多树，一个 DAG，其中每个从单个顶点(红色)可到达的子图是一棵树
{{multiple image
|width2=254<!---adjust to make both images the same height-->
| width2 = 254 < !-调整使两个图像的高度相同
|image1=Polytree.svg|caption1=A [[polytree]], a DAG formed by [[Orientation (graph theory)|orienting]] the edges of an undirected tree
}}
}}
|image2=Butterfly multitree.svg|caption2=A [[multitree]], A DAG in which each subgraph reachable from a single vertex (red) is a tree
A polytree is a directed graph formed by orienting the edges of a free tree. Every polytree is a DAG. In particular, this is true of the arborescences formed by directing all edges outwards from the roots of a tree.
一个多边形是一个有向图形成的定向的边自由树。每棵多叶树都是一个 DAG。特别是，这是真正的树枝形成的所有边缘向外从树根。
|width2=254<!---adjust to make both images the same height-->
}}
A multitree (also called a strongly unambiguous graph or a mangrove) is a directed graph in which there is at most one directed path (in either direction) between any two vertices; equivalently, it is a DAG in which, for every vertex , the subgraph reachable from forms a tree.
多重树(也称为强无歧义图或红树)是一个有向图，其中任意两个顶点之间至多有一条有向路(任意方向) ; 等价地，它是一个有向无环图，其中对于每个顶点，从该子图可达到的子图形成一棵树。
A [[polytree]] is a directed graph formed by orienting the edges of a [[tree (graph theory)|free tree]].<ref>{{citation
| last1 = Rebane
| first1 = George
| last2 = Pearl
| first2 = Judea
| author2-link = Judea Pearl
Topological sorting is the algorithmic problem of finding a topological ordering of a given DAG. It can be solved in linear time. 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. or alternatively, for some topological sorting algorithms, by verifying that the algorithm successfully orders all the vertices without meeting an error condition.
拓扑排序是寻找给定 DAG 的拓扑顺序的计算问题。它可以在线性时间内求解。的拓扑排序算法直接建立顶点排序。它维护了一个顶点列表，这些顶点没有来自其他没有被部分构造的拓扑顺序包括在内的顶点的入射边; 最初这个列表由没有入射边的顶点组成。然后，它重复地从这个列表中添加一个顶点到部分构造的拓扑排序的末尾，并检查它的邻居是否应该添加到这个列表中。当所有顶点都以这种方式被处理时，算法终止。或者，对于某些拓扑排序算法，通过验证算法成功地排序所有顶点，而不满足错误条件。
| contribution = The recovery of causal poly-trees from statistical data
| pages = 222–228
| title = in Proc. 3rd Annual Conference on Uncertainty in Artificial Intelligence (UAI 1987), Seattle, WA, USA, July 1987
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 χ(−1)}}, where is the chromatic polynomial of the given graph.
任何无向图都可以通过为其顶点选择一个总的顺序，并按顺序将前一个端点的每条边定向到后一个端点，从而构成一个 DAG。所得到的边的方向称为无圈方向。不同的总序可能导致相同的无圈取向，因此一个顶点图可以有少于个无圈取向。非循环取向的个数等于 χ (- 1)} ，其中是给定图的色多项式。
| url = ftp://ftp.cs.ucla.edu/tech-report/198_-reports/870031.pdf
| year = 1987
condensation of the blue directed graph. It is formed by contracting each strongly connected component of the blue graph into a single yellow vertex.]]
蓝色有向图的凝聚。它是由蓝色图的每个强连通分量收缩成一个黄色顶点形成的。]
}}{{Dead link|date=July 2019 |bot=InternetArchiveBot |fix-attempted=yes }}.</ref> Every polytree is a DAG. In particular, this is true of the [[Arborescence (graph theory)|arborescences]] formed by directing all edges outwards from the roots of a tree.
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.
任何有向图都可以通过删除一个反馈顶点集或一个反馈弧集、一组顶点或边(分别)来构成一个有向无环图。然而，最小的这样的集合是 np 难以找到。一个任意的有向图也可以通过将每个强连通分量收缩到一个单独的超顶点而转化为 DAG，称为它的凝聚。当图是非循环的时候，它的最小反馈顶点集和反馈弧集是空的，它的缩聚就是图本身。
A [[multitree]] (also called a strongly unambiguous graph or a mangrove) is a directed graph in which there is at most one directed path (in either direction) between any two vertices; equivalently, it is a DAG in which, for every vertex {{mvar|v}}, the subgraph reachable from {{mvar|v}} forms a tree.<ref>{{citation
| last1 = Furnas | first1 = George W. | author1-link = George Furnas
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. 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.
一个给定的有向无环图的传递闭包，包括顶点和边，可以通过使用广度优先搜索或深度优先搜索来测试每个顶点的可达性来及时构造。或者，它可以及时解决在哪里是矩阵乘法算法的指数; 这是一个理论上的改进超过了稠密图的界。
| last2 = Zacks | first2 = Jeff
| contribution = Multitrees: enriching and reusing hierarchical structure
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.
在所有这些传递闭包算法中，可以区分至少一条长度为2条或更多的路径可到达的顶点对和只能通过一条长度为1条路径连接的顶点对。传递约简由形成长度的边组成——一条路径是连接其端点的唯一路径。因此，传递约简可以在与传递闭包相同的渐近时间范围内构造。
| doi = 10.1145/191666.191778
| pages = 330–336
| title = Proc. SIGCHI conference on Human Factors in Computing Systems (CHI '94)
| year = 1994| isbn = 978-0897916509 | s2cid = 18710118 }}.</ref>
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.
闭包问题以一个顶点加权有向无环图为输入，寻求一个闭包的最小(或最大)权重-一组顶点 c，这样没有边离开 c。这个问题可以在没有无环性假设的情况下表示为有向图，但没有更大的一般性，因为在这种情况下，它等价于图的凝聚上的同样问题。通过对最大流问题的约简，可以在多项式时间内求解。
== Computational problems ==
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. In contrast, for arbitrary graphs the shortest path may require slower algorithms such as Dijkstra's algorithm or the Bellman–Ford algorithm, and longest paths in arbitrary graphs are NP-hard to find.
基于拓扑排序原理，有些算法用在 DAGs 上代替一般图时变得更简单。例如，通过处理拓扑有序中的顶点，并计算每个顶点的路径长度为通过任一传入边得到的最小或最大长度，可以在线性时间内从给定的 DAGs 顶点找到最短路径和最长路径。相反，对于任意图，最短路径可能需要较慢的算法，如 Dijkstra 算法或 Bellman-Ford 算法，而任意图中的最长路径是 np 难以找到的。
=== Topological sorting and recognition ===
{{Main|Topological sorting}}
[[Topological sorting]] is the algorithmic problem of finding a topological ordering of a given DAG. It can be solved in [[linear time]].<ref name="clrs">{{Introduction to Algorithms|edition=2|mode=cs2}} Section 22.4, Topological sort, pp. 549–552.</ref> 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.<ref name="j50" /> Alternatively, a topological ordering may be constructed by reversing a [[postorder]] numbering of a [[depth-first search]] graph traversal.<ref name="clrs" />
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 valid<ref>For [[depth-first search]] based topological sorting algorithm, this validity check can be interleaved with the topological sorting algorithm itself; see e.g. {{citation|title=The Algorithm Design Manual|first=Steven S.|last=Skiena|publisher=Springer|year=2009|isbn=978-1-84800-070-4|pages=179–181|url=https://books.google.com/books?id=7XUSn0IKQEgC&pg=PA179}}.</ref> or alternatively, for some topological sorting algorithms, by verifying that the algorithm successfully orders all the vertices without meeting an error condition.<ref name="j50">{{harvtxt|Jungnickel|2012}}, pp. 50–51.</ref>
Directed acyclic graphs representations of partial orderings have many applications in scheduling for systems of tasks with ordering constraints.
偏序的有向无圈图表示在有序约束的任务系统的调度中有许多应用。
An important class of problems of this type concern collections of objects that need to be updated, such as the cells of a spreadsheet after one of the cells has been changed, or the object files of a piece of computer software after its source code has been changed.
这种类型的一类重要问题涉及需要更新的对象集合，例如电子表格中某个单元格更改后的单元格，或者计算机软件中某个源代码更改后的目标文件。
=== Construction from cyclic graphs ===
In this context, a dependency graph is a graph that has a vertex for each object to be updated, and an edge connecting two objects whenever one of them needs to be updated earlier than the other. A cycle in this graph is called a circular dependency, and is generally not allowed, because there would be no way to consistently schedule the tasks involved in the cycle.
在此上下文中，依赖关系图是一个图，其中每个要更新的对象都有一个顶点，并且每当其中一个对象需要比另一个更早更新时，就有一条连接两个对象的边。这个图中的循环称为循环依赖，通常不允许这样做，因为没有办法始终如一地安排循环中涉及的任务。
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 (graph theory)|orientation]] of the edges is called an [[acyclic orientation]]. Different total orders may lead to the same acyclic orientation, so an {{mvar|n}}-vertex graph can have fewer than {{math|''n''!}} acyclic orientations. The number of acyclic orientations is equal to {{math|{{!}}''χ''(−1){{!}}}}, where {{mvar|χ}} is the [[chromatic polynomial]] of the given graph.<ref>{{citation|first=Richard P.|last=Stanley|author-link=Richard P. Stanley|title=Acyclic orientations of graphs|journal=Discrete Mathematics|volume=5|issue=2 |pages=171–178|year= 1973|doi=10.1016/0012-365X(73)90108-8|url=http://math.mit.edu/~rstan/pubs/pubfiles/18.pdf}}.</ref>
Dependency graphs without circular dependencies form DAGs.
无循环依赖关系的依赖图形成 DAGs。
[[File:Graph Condensation.svg|thumb|upright=1.5|The yellow directed acyclic graph is the [[Condensation (graph theory)|condensation]] of the blue directed graph. It is formed by [[Edge contraction|contracting]] each [[strongly connected component]] of the blue graph into a single yellow vertex.]]
For instance, when one cell of a spreadsheet changes, it is necessary to recalculate the values of other cells that depend directly or indirectly on the changed cell. For this problem, the tasks to be scheduled are the recalculations of the values of individual cells of the spreadsheet. Dependencies arise when an expression in one cell uses a value from another cell. In such a case, the value that is used must be recalculated earlier than the expression that uses it. Topologically ordering the dependency graph, and using this topological order to schedule the cell updates, allows the whole spreadsheet to be updated with only a single evaluation per cell. Similar problems of task ordering arise in makefiles for program compilation
例如，当电子表格的一个单元格发生更改时，必须重新计算直接或间接依赖于更改单元格的其他单元格的值。对于此问题，计划中的任务是对电子表格各单元格的值重新计算。当一个单元格中的表达式使用另一个单元格中的值时，就会出现依赖性。在这种情况下，必须比使用该值的表达式更早地重新计算使用的值。通过拓扑排序依赖关系图，并使用这个拓扑有序表来安排单元格的更新，可以使整个电子表格只需要对每个单元格进行一次计算就可以更新。类似的任务排序问题也出现在程序编译的 makefile 中
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.<ref>{{Garey-Johnson}}, Problems GT7 and GT8, pp. 191–192.</ref> An arbitrary directed graph may also be transformed into a DAG, called its [[condensation (graph theory)|condensation]], by [[Edge contraction|contracting]] each of its [[strongly connected component]]s into a single supervertex.<ref>{{citation|title=Structural Models: An Introduction to the Theory of Directed Graphs|last1=Harary|first1=Frank|author1-link=Frank Harary|last2=Norman|first2=Robert Z.|last3=Cartwright|first3=Dorwin|publisher=John Wiley & Sons|year=1965|page=63}}.</ref> When the graph is already acyclic, its smallest feedback vertex sets and feedback arc sets are [[empty set|empty]], and its condensation is the graph itself.
PERT chart for a project with five milestones (labeled 10–50) and six tasks (labeled A–F). There are two critical paths, ADF and BC.
有五个里程碑(标记为10-50)和六个任务(标记为 a-f)的项目的 PERT 图表。有两条关键路径，ADF 和 BC。
=== Transitive closure and transitive reduction ===
A somewhat different DAG-based formulation of scheduling constraints is used by the program evaluation and review technique (PERT), a method for management of large human projects that was one of the first applications of DAGs. In this method, the vertices of a DAG represent milestones of a project rather than specific tasks to be performed. Instead, a task or activity is represented by an edge of a DAG, connecting two milestones that mark the beginning and completion of the task. Each such edge is labeled with an estimate for the amount of time that it will take a team of workers to perform the task. The longest path in this DAG represents the critical path of the project, the one that controls the total time for the project. Individual milestones can be scheduled according to the lengths of the longest paths ending at their vertices.
计划评审技术(program evaluation and review technique，PERT)使用了一种略有不同的基于 DAGs 的进度约束形式，这种方法是 DAGs 的首批应用之一，用于管理大型人类项目。在这种方法中，DAG 的顶点代表项目的里程碑，而不是要执行的具体任务。相反，一个任务或活动由一个有向无环图的边缘表示，连接两个标志任务开始和完成的里程碑。每个这样的边都标注了一个估计值，表示一组工作人员执行该任务所需的时间。DAG 中最长的路径代表项目的关键路径，它控制项目的总时间。单个里程碑可以根据在其顶点结束的最长路径的长度进行调度。
The transitive closure of a given DAG, with {{mvar|n}} vertices and {{mvar|m}} edges, may be constructed in time {{math|''O''(''mn'')}} by using either [[breadth-first search]] or [[depth-first search]] to test reachability from each vertex.<ref>{{harvtxt|Skiena|2009}}, p. 495.</ref> Alternatively, it can be solved in time {{math|''O''(''n''<sup>''ω''</sup>)}} where {{math|''ω'' < 2.373}} is the [[Computational complexity of matrix multiplication#Matrix multiplication exponent|exponent for matrix multiplication algorithms]]; this is a theoretical improvement over the {{math|''O''(''mn'')}} bound for [[dense graph]]s.<ref>{{harvtxt|Skiena|2009}}, p. 496.</ref>
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.<ref>{{harvtxt|Bang-Jensen|Gutin|2008}}, p. 38.</ref>
A directed acyclic graph may be used to represent a network of processing elements. In this representation, data enters a processing element through its incoming edges and leaves the element through its outgoing edges.
有向无环图可以用来表示处理元素的网络。在这种表示法中，数据通过传入边进入处理元素，通过传出边离开元素。
=== Closure problem ===
For instance, in electronic circuit design, static combinational logic blocks can be represented as an acyclic system of logic gates that computes a function of an input, where the input and output of the function are represented as individual bits. In general, the output of these blocks cannot be used as the input unless it is captured by a register or state element which maintains its acyclic properties. Electronic circuit schematics either on paper or in a database are a form of directed acyclic graphs using instances or components to form a directed reference to a lower level component. Electronic circuits themselves are not necessarily acyclic or directed.
例如，在电子电路设计中，静态组合逻辑电路块可以表示为一个逻辑门的非循环系统，计算一个输入函数，其中的输入和输出被表示为单独的位。一般来说，这些块的输出不能用作输入，除非它被保持其非循环属性的寄存器或状态元素捕获。纸上或数据库中的电子电路原理图是一种有向无环图的形式，使用实例或组件形成对较低级别组件的有向引用。电子电路本身不一定是无环或有向的。
{{Main|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]].<ref>{{citation
Dataflow programming languages describe systems of operations on data streams, and the connections between the outputs of some operations and the inputs of others. These languages can be convenient for describing repetitive data processing tasks, in which the same acyclically-connected collection of operations is applied to many data items. They can be executed as a parallel algorithm in which each operation is performed by a parallel process as soon as another set of inputs becomes available to it.
数据流编程语言描述了对数据流的操作系统，以及某些操作的输出和其他操作的输入之间的连接。这些语言可以方便地描述重复的数据处理任务，在这些任务中，对许多数据项应用相同的无环连接的操作集合。它们可以作为一个并行算法执行，其中每个操作在另一组输入可用时由一个并行进程执行。
| last = Picard | first = Jean-Claude
| doi = 10.1287/mnsc.22.11.1268
In compilers, straight line code (that is, sequences of statements without loops or conditional branches) may be represented by a DAG describing the inputs and outputs of each of the arithmetic operations performed within the code. This representation allows the compiler to perform common subexpression elimination efficiently. At a higher level of code organization, the acyclic dependencies principle states that the dependencies between modules or components of a large software system should form a directed acyclic graph.
在编译器中，直线代码(即没有循环或条件分支的语句序列)可以由 DAG 表示，DAG 描述代码中执行的每个算术运算的输入和输出。此表示形式允许编译器有效地执行公共子表达式消除。在更高层次的代码组织中，非循环依赖原则指出，大型软件系统的模块或组件之间的依赖应该形成一个有向无环图。
| issue = 11
| journal = [[Management Science (journal)|Management Science]]
Feedforward neural networks are another example.
前馈神经网络是另一个例子。
| mr = 0403596
| pages = 1268–1272
| title = Maximal closure of a graph and applications to combinatorial problems
| volume = 22
Graphs in which vertices represent events occurring at a definite time, and where the edges are always point from the early time vertex to a late time vertex of the edge, are necessarily directed and acyclic. The lack of a cycle follows because the time associated with a vertex always increases as you follow any path in the graph so you can never return to a vertex on a path. This reflects our natural intuition that causality means events can only affect the future, they never affect the past, and thus we have no causal loops. An example of this type of directed acyclic graph are those encountered in the causal set approach to quantum gravity though in this case the graphs considered are transitively complete. In the version history example, each version of the software is associated with a unique time, typically the time the version was saved, committed or released. For citation graphs, the documents are published at one time and can only refer to older documents.
顶点表示在一定时间内发生的事件，并且边始终是从边的早期时间顶点到后期时间顶点的点的图，必然是有向的和无环的。没有循环是因为当你沿着图中的任何一条路径走时，与一个顶点相关的时间总是增加，所以你永远不能返回到路径上的一个顶点。这反映了我们的自然直觉，因果关系意味着事件只能影响未来，它们从不影响过去，因此我们没有因果循环。这类有向无环图的一个例子是在量子引力的因果集方法中遇到的，尽管在这种情况下所考虑的图是传递完全的。在版本历史示例中，软件的每个版本都与一个唯一的时间相关联，通常是保存、提交或发布版本的时间。对于引用图，这些文献只能发表一次，并且只能引用较早的文献。
| year = 1976}}.</ref>
Sometimes events are not associated with a specific physical time. Provided that pairs of events have a purely causal relationship, that is edges represent causal relations between the events, we will have a directed acyclic graph. For instance, a Bayesian network represents a system of probabilistic events as vertices in a directed acyclic graph, in which the likelihood of an event may be calculated from the likelihoods of its predecessors in the DAG. In this context, the moral graph of a DAG is the undirected graph created by adding an (undirected) edge between all parents of the same vertex (sometimes called marrying), and then replacing all directed edges by undirected edges. Another type of graph with a similar causal structure is an influence diagram, the vertices of which represent either decisions to be made or unknown information, and the edges of which represent causal influences from one vertex to another. In epidemiology, for instance, these diagrams are often used to estimate the expected value of different choices for intervention.
有时，事件与特定的物理时间无关。如果成对的事件具有纯粹的因果关系，即边缘代表事件之间的因果关系，那么我们就有了一个有向无环图。例如，一个贝氏网路代表一个概率事件系统作为一个有向无环图中的顶点，在这个顶点中，一个事件的可能性可以通过它在 DAG 中的前身的可能性来计算。在这种情况下，有向无环图是在同一顶点的所有父母之间加上一条(无向)边(有时称为结合) ，然后用无向边代替所有有向边而产生的无向图。另一种具有类似因果结构的图类型是影响图，其顶点表示要作出的决定或未知信息，其边表示从一个顶点到另一个顶点的因果影响。例如，在流行病学中，这些图表通常用于估计不同干预选择的期望值。
=== 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 path]]s and [[longest path problem|longest paths]] from a given starting vertex in DAGs in linear time by [[Topological sorting#Application to shortest path finding|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.<ref>Cormen et al. 2001, Section 24.2, Single-source shortest paths in directed acyclic graphs, pp. 592–595.</ref> In contrast, for arbitrary graphs the shortest path may require slower algorithms such as [[Dijkstra's algorithm]] or the [[Bellman–Ford algorithm]],<ref>Cormen et al. 2001, Sections 24.1, The Bellman–Ford algorithm, pp. 588–592, and 24.3, Dijkstra's algorithm, pp. 595–601.</ref> and longest paths in arbitrary graphs are [[NP-hard]] to find.<ref>Cormen et al. 2001, p. 966.</ref>
The converse is also true. That is in any application represented by a directed acyclic graph there is a causal structure, either an explicit order or time in the example or an order which can be derived from graph structure. This follows because all directed acyclic graphs have a topological ordering, i.e. there is at least one way to put the vertices in an order such that all edges point in the same direction along that order.
反之亦然。也就是说，在任何用有向无环图表示的应用程序中，都存在一个因果结构，要么是例子中显式的顺序或时间，要么是可以从图结构中派生出来的顺序。这是因为所有有向无圈图都有一个拓扑序，即。至少有一种方法可以将顶点按顺序排列，使所有边沿着这个顺序指向同一个方向。
== Applications ==
Family tree of the [[Ptolemaic dynasty, with many marriages between close relatives causing pedigree collapse]]
托勒密王朝的家谱，许多近亲之间的婚姻导致家谱崩溃
=== Scheduling ===
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" relationships between women) and patrilineal descent ("father" relationships between men) are trees within this graph. Because
家族树可以看作是有向无圈图，每个家族成员有一个顶点，每个亲子关系有一条边。除了名字，这些图并不一定是树，因为亲戚之间的婚姻(所以一个孩子在母亲和父亲方面有一个共同的祖先)会导致家谱崩溃。母系血统(女性之间的“母亲”关系)和父系血统(男性之间的“父亲”关系)的图表就是这个图表中的树。因为
Directed acyclic graphs representations of partial orderings have many applications in [[Schedule|scheduling]] for systems of tasks with ordering constraints.<ref>{{harvtxt|Skiena|2009}}, p. 469.</ref>
no one can become their own ancestor, family trees are acyclic.
没有人能成为自己的祖先，家谱是无环的。
An important class of problems of this type concern collections of objects that need to be updated, such as the cells of a [[spreadsheet]] after one of the cells has been changed, or the [[object file]]s of a piece of computer software after its [[source code]] has been changed.
In this context, a [[dependency graph]] is a graph that has a vertex for each object to be updated, and an edge connecting two objects whenever one of them needs to be updated earlier than the other. A cycle in this graph is called a [[circular dependency]], and is generally not allowed, because there would be no way to consistently schedule the tasks involved in the cycle.
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.
分散式版本控制版本的历史，比如 Git，通常有一个有向无环图版本的结构，每个版本都有一个顶点，一条边连接直接从其他版本派生出来的修订对。由于合并，这些通常不是树。
Dependency graphs without circular dependencies form DAGs.<ref>{{citation | last1=Al-Mutawa | first1=H. A. | last2=Dietrich | first2=J. | last3=Marsland | first3=S. | last4=McCartin | first4=C. | contribution=On the shape of circular dependencies in Java programs | doi=10.1109/ASWEC.2014.15 | pages=48–57 | publisher=IEEE | title=23rd Australian Software Engineering Conference | year=2014| isbn=978-1-4799-3149-1 | s2cid=17570052 }}.</ref>
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 .
在计算几何的许多随机算法中，该算法维护一个历史 DAG，它表示一个几何结构在一系列结构变化过程中的版本历史。例如，在一个随机增量的三角形算法中，每增加一个点，三角形就被三个更小的三角形替换，或者用一对不同的三角形“翻转”操作替换成对的三角形，从而改变了三角形德劳内三角化。该算法的历史 DAG 包含每个三角形的顶点，以及每个三角形到其他两三个三角形的边。这种结构允许有效地回答点位置查询: 要在德劳内三角化中找到查询点的位置，按照历史 DAG 中的路径，在每一步移动到包含的替换三角形。在这条路径中达到的最后一个三角形必须是包含。
For instance, when one cell of a [[spreadsheet]] changes, it is necessary to recalculate the values of other cells that depend directly or indirectly on the changed cell. For this problem, the tasks to be scheduled are the recalculations of the values of individual cells of the spreadsheet. Dependencies arise when an expression in one cell uses a value from another cell. In such a case, the value that is used must be recalculated earlier than the expression that uses it. Topologically ordering the dependency graph, and using this topological order to schedule the cell updates, allows the whole spreadsheet to be updated with only a single evaluation per cell.<ref name="hgt1181">{{citation |title=Handbook of Graph Theory |first1=Jonathan L. |last1=Gross |first2=Jay |last2=Yellen |first3=Ping |last3=Zhang | author3-link = Ping Zhang (graph theorist)|edition=2nd |publisher=CRC Press |year=2013 |isbn=978-1-4398-8018-0 |page=1181 |url=https://books.google.com/books?id=cntcAgAAQBAJ&pg=PA1181}}.</ref> Similar problems of task ordering arise in [[makefile]]s for program compilation<ref name="hgt1181" /> and [[instruction scheduling]] for low-level computer program optimization.<ref>{{citation |title=The Compiler Design Handbook: Optimizations and Machine Code Generation |first1=Y. N. |last1=Srikant |first2=Priti |last2=Shankar |edition=2nd |publisher=CRC Press|year=2007 |isbn=978-1-4200-4383-9 |pages=19–39 |url=https://books.google.com/books?id=1kqAv-uDEPEC&pg=SA19-PA39}}.</ref>
[[File:Pert chart colored.svg|thumb|PERT chart for a project with five milestones (labeled 10–50) and six tasks (labeled A–F). There are two critical paths, ADF and BC.]]
In a citation graph the vertices are documents with a single publication date. The edges represent the citations from the bibliography of one document to other necessarily earlier documents. The classic example comes from the citations between academic papers as pointed out in the 1965 article "Networks of Scientific Papers" by Derek J. de Solla Price who went on to produce the first model of a citation network, the Price model. In this case the citation count of a paper is just the in-degree of the corresponding vertex of the citation network. This is an important measure in citation analysis. Court judgements provide another example as judges support their conclusions in one case by recalling other earlier decisions made in previous cases. A final example is provided by patents which must refer to earlier prior art, earlier patents which are relevant to the current patent claim. By taking the special properties of directed acyclic graphs into account, one can analyse citation networks with techniques not available when analysing the general graphs considered in many studies using network analysis. For instance transitive reduction gives a new insights into the citation distributions found in different applications highlighting clear differences in the mechanisms creating citations networks in different contexts. Another technique is main path analysis, which traces the citation links and suggests the most significant citation chains in a given citation graph.
在引用图中，顶点是只有一个出版日期的文档。边代表从一个文档的参考书目到其他必要的早期文档的引用。经典的例子来自于学术论文之间的引用，正如1965年德瑞克·约翰·德索拉·普莱斯在《科学论文网络》一文中指出的那样，他继续创造了引用网络的第一个模型---- 价格模型。在这种情况下，一篇论文的引文数量就是引文网络相应顶点的度数。这是21引文分析的一项重要措施。法院判决提供了另一个例子，因为法官通过回顾以前案件中作出的其他判决来支持他们在一个案件中的结论。最后一个例子是专利，必须提到先前的技术，先前的专利，这是有关当前的专利权利主张。通过考虑有向无环图的特殊性质，可以利用网络分析方法分析引文网络。例如，传递减法对不同应用中的引用分布提供了新的见解，突出了不同上下文中引用网络形成机制的明显差异。另一种技术是主路径分析，它跟踪引文链接，并提出给定引文图中最重要的引文链。
A somewhat different DAG-based formulation of scheduling constraints is used by the [[program evaluation and review technique]] (PERT), a method for management of large human projects that was one of the first applications of DAGs. In this method, the vertices of a DAG represent [[Milestone (project management)|milestones]] of a project rather than specific tasks to be performed. Instead, a task or activity is represented by an edge of a DAG, connecting two milestones that mark the beginning and completion of the task. Each such edge is labeled with an estimate for the amount of time that it will take a team of workers to perform the task. The [[Longest path problem|longest path]] in this DAG represents the [[Critical path method|critical path]] of the project, the one that controls the total time for the project. Individual milestones can be scheduled according to the lengths of the longest paths ending at their vertices.<ref>{{citation |title=What Every Engineer Should Know About Decision Making Under Uncertainty |first=John X. |last=Wang |publisher=CRC Press |year=2002 |isbn=978-0-8247-4373-4 |page=160 |url=https://books.google.com/books?id=C3yKML0dUVIC&pg=PA160}}.</ref>
The Price model is too simple to be a realistic model of a citation network but it is simple enough to allow for analytic solutions for some of its properties. Many of these can be found by using results derived from the undirected version of the Price model, the Barabási–Albert model. However, since Price's model gives a directed acyclic graph, it is a useful model when looking for analytic calculations of properties unique to directed acyclic graphs. For instance,
普莱斯模型过于简单，不可能成为引文网络的现实模型，但它足够简单，可以为其某些属性提供分析解。其中许多问题可以通过使用从价格模型(Barabási-Albert 模型)的无向版本得出的结果来找到。然而，由于 Price 的模型给出了一个有向无环图，所以在寻找有向无圈图所特有的性质的解析计算时，它是一个很有用的模型。比如说,
=== Data processing networks ===
the length of the longest path, from the n-th node added to the network to the first node in the network, scales as <math>\ln(n)</math>.
最长路径的长度，从添加到网络的第 n 个节点到网络中的第一个节点，缩放为 < math > ln (n) </math > 。
A directed acyclic graph may be used to represent a network of processing elements. In this representation, data enters a processing element through its incoming edges and leaves the element through its outgoing edges.
For instance, in electronic circuit design, static [[combinational logic]] blocks can be represented as an acyclic system of [[logic gate]]s that computes a function of an input, where the input and output of the function are represented as individual [[bit]]s. In general, the output of these blocks cannot be used as the input unless it is captured by a register or state element which maintains its acyclic properties.<ref>{{citation|title=Timing|first=Sachin|last=Sapatnekar|publisher=Springer|year=2004|isbn=978-1-4020-7671-8|page=133|url=https://books.google.com/books?id=fL9k-VkZVr0C&pg=PA133}}.</ref> Electronic circuit schematics either on paper or in a database are a form of directed acyclic graphs using instances or components to form a directed reference to a lower level component. Electronic circuits themselves are not necessarily acyclic or directed.
Directed acyclic graphs may also be used as a compact representation of a collection of sequences. In this type of application, one finds a DAG in which the paths form the given sequences. When many of the sequences share the same subsequences, these shared subsequences can be represented by a shared part of the DAG, allowing the representation to use less space than it would take to list out all of the sequences separately. For example, the directed acyclic word graph is a data structure in computer science formed by a directed acyclic graph with a single source and with edges labeled by letters or symbols; the paths from the source to the sinks in this graph represent a set of strings, such as English words. Any set of sequences can be represented as paths in a tree, by forming a tree vertex for every prefix of a sequence and making the parent of one of these vertices represent the sequence with one fewer element; the tree formed in this way for a set of strings is called a trie. A directed acyclic word graph saves space over a trie by allowing paths to diverge and rejoin, so that a set of words with the same possible suffixes can be represented by a single tree vertex.
有向无环图也可用作序列集合的紧凑表示。在这种类型的应用程序中，人们会找到一个 DAG，其中的路径形成给定的序列。当许多序列共享相同的子序列时，这些共享子序列可以由 DAG 的一个共享部分来表示，这使得这种表示比单独列出所有序列所需要的空间更少。例如，有向无环词图是计算机科学中的一种数据结构，由一个单源的有向无环图构成，其边缘用字母或符号标记; 在这个图中，从源到汇的路径表示一组字符串，例如英语单词。任何一组序列都可以表示为树中的路径，方法是为序列的每个前缀形成一个树顶点，并使其中一个顶点的父顶点表示只有一个元素的序列; 对于一组字符串以这种方式形成的树称为 trie。有向无环词图允许路径发散和重新连接，从而在一个三元图上节省空间，这样一组可能具有相同后缀的词可以由一个树顶点表示。
[[Dataflow programming]] languages describe systems of operations on [[data stream]]s, and the connections between the outputs of some operations and the inputs of others. These languages can be convenient for describing repetitive data processing tasks, in which the same acyclically-connected collection of operations is applied to many data items. They can be executed as a [[parallel algorithm]] in which each operation is performed by a parallel process as soon as another set of inputs becomes available to it.<ref>{{citation|title=Programming Symposium|series=Lecture Notes in Computer Science|volume=19|year=1974|pages=362–376|contribution=First version of a data flow procedure language|first=Jack B.|last=Dennis|doi=10.1007/3-540-06859-7_145|isbn=978-3-540-06859-4}}.</ref>
The same idea of using a DAG to represent a family of paths occurs in the binary decision diagram, a DAG-based data structure for representing binary functions. In a binary decision diagram, each non-sink vertex is labeled by the name of a binary variable, and each sink and each edge is labeled by a 0 or 1. The function value for any truth assignment to the variables is the value at the sink found by following a path, starting from the single source vertex, that at each non-sink vertex follows the outgoing edge labeled with the value of that vertex's variable. Just as directed acyclic word graphs can be viewed as a compressed form of , binary decision diagrams can be viewed as compressed forms of decision trees that save space by allowing paths to rejoin when they agree on the results of all remaining decisions.
使用 DAG 表示一系列路径的同样想法也出现在二元决策图中，这是一个基于 dags 的数据结构，用于表示二进制函数。在二元决策图中，每个无汇点都用一个二进制变量的名称标记，每个汇点和每条边都用一个0或1标记。任何对变量进行真值赋值的函数值，都是指从单个源顶点开始，沿着一条路径，在每个非汇顶点上沿着标有该顶点变量值的外向边缘，在汇处找到的值。正如有向无环字图可以看作是一种压缩形式，二叉决策图可以看作是一种压缩形式的决策树，通过允许路径在所有剩余决策的结果一致时重新连接来节省空间。
In [[compiler]]s, straight line code (that is, sequences of statements without loops or conditional branches) may be represented by a DAG describing the inputs and outputs of each of the arithmetic operations performed within the code. This representation allows the compiler to perform [[common subexpression elimination]] efficiently.<ref>{{citation|title=Advanced Backend Optimization|first1=Sid|last1=Touati|first2=Benoit|last2=de Dinechin|publisher=John Wiley & Sons|year=2014|isbn=978-1-118-64894-0|page=123|url=https://books.google.com/books?id=nO2-AwAAQBAJ&pg=PA123}}.</ref> At a higher level of code organization, the [[acyclic dependencies principle]] states that the dependencies between modules or components of a large software system should form a directed acyclic graph.<ref>{{citation|title=Large-Scale Software Architecture: A Practical Guide using UML|first1=Jeff|last1=Garland|first2=Richard|last2=Anthony|publisher=John Wiley & Sons|year=2003|isbn=9780470856383|page=215|url=https://books.google.com/books?id=_2oQLLSqZ88C&pg=PA215}}.</ref>
[[Feedforward neural network]]s are another example.
=== Causal structures ===
{{main|Bayesian network}}
Graphs in which vertices represent events occurring at a definite time, and where the edges are always point from the early time vertex to a late time vertex of the edge, are necessarily directed and acyclic. The lack of a cycle follows because the time associated with a vertex always increases as you follow any [[Path (graph theory)|path]] in the graph so you can never return to a vertex on a path. This reflects our natural intuition that causality means events can only affect the future, they never affect the past, and thus we have no [[causal loop]]s. An example of this type of directed acyclic graph are those encountered in the [[Causal sets|causal set approach to quantum gravity]] though in this case the graphs considered are [[#Transitive closure and transitive reduction|transitively complete]]. In the version history example, each version of the software is associated with a unique time, typically the time the version was saved, committed or released. For citation graphs, the documents are published at one time and can only refer to older documents.
Sometimes events are not associated with a specific physical time. Provided that pairs of events have a purely causal relationship, that is edges represent [[causality|causal relations]] between the events, we will have a directed acyclic graph.<ref>{{citation|title=Causal Learning|first1=Alison|last1=Gopnik|first2=Laura|last2=Schulz|publisher=Oxford University Press|year=2007|isbn=978-0-19-803928-0|page=4|url=https://books.google.com/books?id=35MKXlKoXIUC&pg=PA4}}.</ref> For instance, a [[Bayesian network]] represents a system of probabilistic events as vertices in a directed acyclic graph, in which the likelihood of an event may be calculated from the likelihoods of its predecessors in the DAG.<ref>{{citation|title=Probabilistic Boolean Networks: The Modeling and Control of Gene Regulatory Networks|publisher=Society for Industrial and Applied Mathematics|first1=Ilya|last1=Shmulevich|first2=Edward R.|last2=Dougherty|year=2010|isbn=978-0-89871-692-4|page=58|url=https://books.google.com/books?id=RfshqEgO7KgC&pg=PA58}}.</ref> In this context, the [[moral graph]] of a DAG is the undirected graph created by adding an (undirected) edge between all parents of the same vertex (sometimes called ''marrying''), and then replacing all directed edges by undirected edges.<ref>{{citation |last1= Cowell |first1= Robert G. |author2-link=Philip Dawid|last2=Dawid|first2=A. Philip|author3-link=Steffen Lauritzen|last3=Lauritzen|first3=Steffen L.|author4-link=David Spiegelhalter|last4=Spiegelhalter|first4=David J.|title= Probabilistic Networks and Expert Systems |publisher= Springer |year= 1999 |isbn= 978-0-387-98767-5 |chapter= 3.2.1 Moralization|pages= 31–33 }}.</ref> Another type of graph with a similar causal structure is an [[influence diagram]], the vertices of which represent either decisions to be made or unknown information, and the edges of which represent causal influences from one vertex to another.<ref>{{citation|title=The Technology Management Handbook|first=Richard C.|last=Dorf|publisher=CRC Press|year=1998|isbn=978-0-8493-8577-3|page=9{{hyphen}}7<!-- Do not conver this hyphen into a dash! It is a section-page number, not a range of page numbers. -->|url=https://books.google.com/books?id=C2u8I0DFo4IC&pg=SA9-PA7}}.</ref> In [[epidemiology]], for instance, these diagrams are often used to estimate the expected value of different choices for intervention.<ref>{{citation|title=Encyclopedia of Epidemiology, Volume 1|first=Sarah|last=Boslaugh|publisher=SAGE|year=2008|isbn=978-1-4129-2816-8|page=255|url=https://books.google.com/books?id=wObgnN3x14kC&pg=PA255}}.</ref><ref name="pearl:95">{{citation | last = Pearl | first = Judea | doi = 10.1093/biomet/82.4.669 | issue = 4 | journal = Biometrika | pages = 669–709 | title = Causal diagrams for empirical research | volume = 82 | year = 1995| url = https://escholarship.org/uc/item/6gv9n38c }}.</ref>
Category:Directed graphs
类别: 有向图
Category:Directed acyclic graphs
范畴: 有向无圈图
The converse is also true. That is in any application represented by a directed acyclic graph there is a causal structure, either an explicit order or time in the example or an order which can be derived from graph structure. This follows because all directed acyclic graphs have a [[#Topological ordering|topological ordering]], i.e. there is at least one way to put the vertices in an order such that all edges point in the same direction along that order.
de:Graph (Graphentheorie)#Teilgraphen.2C Wege und Zyklen
de:Graph (Graphentheorie)#Teilgraphen.2C Wege und Zyklen
<noinclude>
<small>This page was moved from [[wikipedia:en:Directed acyclic graph]]. Its edit history can be viewed at [[有向无环图/edithistory]]</small></noinclude>
[[Category:待整理页面]]
{{short description|Directed graph with no directed cycles}}
{{good article}}
[[File:Tred-G.svg|thumb|Example of a directed acyclic graph.]]
Example of a directed acyclic graph.
有向无环图的例子。
In [[mathematics]], particularly [[graph theory]], and [[computer science]], a '''directed acyclic graph''' ('''DAG''' or '''dag''' {{IPAc-en|audio=en-us-DAG.ogg|ˈ|d|æ|g}}) is a [[directed graph]] with no [[Cycle graph#Directed cycle graph|directed cycles]]. That is, it consists of [[Vertex (graph theory)|vertices]] and [[edge (graph theory)|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 [[topological ordering|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 sociology (citation networks) to computation (scheduling).
In mathematics, particularly graph theory, and computer science, a directed acyclic graph (DAG or 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 sociology (citation networks) to computation (scheduling).
在数学，特别是图论和计算机科学中，有向无环图图(DAG 或 DAG)是一个没有有向圈的有向图。也就是说，它由顶点和边(也称为弧)组成，每条边都从一个顶点指向另一个顶点，这样沿着这些方向走永远不会形成一个闭合的循环。有向图是一个有向无环图当且仅当它可以通过将顶点按照与所有边方向一致的线性顺序排列而拓扑排序。DAGs 有许多科学和计算应用，从生物学(进化论，家族树，流行病学)到社会学(引文网络)到计算(调度)。
==Definitions==
A [[Graph (discrete mathematics)|graph]] is formed by [[vertex (graph theory)|vertices]] and by [[edge (graph theory)|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 [[Path (graph theory)|path]] in a directed graph is a sequence of edges having the property that the ending vertex of each edge in the sequence is the same as the starting vertex of the next edge in the sequence; a path forms a cycle if the starting vertex of its first edge equals the ending vertex of its last edge. A directed acyclic graph is a directed graph that has no cycles.<ref name="thul">{{citation|title=Graphs: Theory and Algorithms|first1=K.|last1=Thulasiraman|first2=M. N. S.|last2=Swamy|publisher=John Wiley and Son|year=1992|isbn=978-0-471-51356-8|contribution=5.7 Acyclic Directed Graphs|page=118}}.</ref><ref name="bang">{{citation|title=Digraphs: Theory, Algorithms and Applications|first1=Jørgen|last1=Bang-Jensen|series=Springer Monographs in Mathematics|edition=2nd|publisher=Springer-Verlag|year=2008|isbn=978-1-84800-997-4|contribution=2.1 Acyclic Digraphs|pages=32–34}}.</ref><ref>{{citation|title=Graph theory: an algorithmic approach|first=Nicos|last=Christofides|author-link=Nicos Christofides|publisher=Academic Press|year=1975|pages=170–174}}.</ref>
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 path in a directed graph is a sequence of edges having the property that the ending vertex of each edge in the sequence is the same as the starting vertex of the next edge in the sequence; a path forms a cycle if the starting vertex of its first edge equals the ending vertex of its last edge. A directed acyclic graph is a directed graph that has no cycles.
图是由顶点和连接顶点对的边组成的，顶点可以是任何一种由边成对连接的对象。在有向图的情况下，每条边都有一个方向，从一个顶点到另一个顶点。有向图中的路是一个边序列，它具有序列中每条边的结束顶点与序列中下一条边的起始顶点相同的性质; 如果一条路的第一条边的起始顶点与它的最后一条边的结束顶点相等，那么它就形成了一个圈。有向无环图是一个没有圈的有向图。
A vertex {{mvar|v}} of a directed graph is said to be [[Reachability|reachable]] from another vertex {{mvar|u}} when there exists a path that starts at {{mvar|u}} and ends at {{mvar|v}}. As a special case, every vertex is considered to be reachable from itself (by a path with zero edges). If a vertex can reach itself via a nontrivial path (a path with one or more edges), then that path is a cycle, so another way to define directed acyclic graphs is that they are the graphs in which no vertex can reach itself via a nontrivial path.<ref>{{citation|title=Simulation Techniques for Discrete Event Systems|volume=14|series=Cambridge Computer Science Texts|first=I.|last=Mitrani|year=1982|publisher=Cambridge University Press|isbn=9780521282826|page=27|url=https://books.google.com/books?id=CF04AAAAIAAJ&pg=PA27}}.</ref>
A vertex of a directed graph is said to be reachable from another vertex when there exists a path that starts at and ends at . As a special case, every vertex is considered to be reachable from itself (by a path with zero edges). If a vertex can reach itself via a nontrivial path (a path with one or more edges), then that path is a cycle, so another way to define directed acyclic graphs is that they are the graphs in which no vertex can reach itself via a nontrivial path.
有向图的一个顶点称为从另一个顶点到达的，当存在一条从点开始到点结束的路时。作为一种特殊情况，每个顶点都被认为是从它自身可到达的(通过一条零边的路径)。如果一个顶点可以通过一条非平凡的路(一条有一条或多条边的路)到达它自己，那么这条路就是一个圈，因此定义有向无圈图的另一种方法是，它们是图中没有顶点可以通过一条非平凡的路到达它自己。
== Mathematical properties ==
=== Reachability, transitive closure, and transitive reduction ===
{{multiple image|image1=Tred-G.svg|width1=175|image2=Tred-Gprime.svg|width2=124|caption1=A DAG {{mvar|G}}|caption2=Transitive reduction of {{mvar|G}}}}
The [[reachability]] relationship in any directed acyclic graph can be formalized as a [[partial order]] {{math|≤}} on the vertices of the DAG. In this partial order, two vertices {{mvar|u}} and {{mvar|v}} are ordered as {{math|''u'' ≤ ''v''}} exactly when there exists a directed path from {{mvar|u}} to {{mvar|v}} in the DAG; that is, when {{mvar|v}} is reachable from {{mvar|u}}.<ref>{{citation|title=The Design and Analysis of Algorithms|series=Monographs in Computer Science|first=Dexter|last=Kozen|author-link=Dexter Kozen|publisher=Springer|year=1992|isbn=978-0-387-97687-7|page=9|url=https://books.google.com/books?id=L_AMnf9UF9QC&pg=PA9}}.</ref> However, different DAGs may give rise to the same reachability relation and the same partial order.<ref>{{citation|title=Loop Transformations for Restructuring Compilers: The Foundations|first=Utpal|last=Banerjee|publisher=Springer|year=1993|isbn=978-0-7923-9318-4|page=19|contribution=Exercise 2(c)|url=https://books.google.com/books?id=Cog7zSSlqFwC&pg=PA19}}.</ref> For example, the DAG with two edges {{math|''a'' → ''b''}} and {{math|''b'' → ''c''}} has the same reachability relation as the graph with three edges {{math|''a'' → ''b''}}, {{math|''b'' → ''c''}}, and {{math|''a'' → ''c''}}. Both of these DAGS produce the same partial order, in which the vertices are ordered as {{math|''a'' ≤ ''b'' ≤ ''c''}}.
The reachability relationship in any directed acyclic graph 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 is reachable from . However, different DAGs may give rise to the same reachability relation and the same partial order. For example, the DAG with two edges and has the same reachability relation as the graph with three edges , , and . Both of these DAGS produce the same partial order, in which the vertices are ordered as .
任何有向无环图中的可达关系都可以形式化为 DAG 顶点上的一个偏序。在这个部分顺序中，两个顶点的顺序与有向无环图中存在从到的有向路径时的顺序完全一致; 也就是说，当从。然而，不同的 DAGs 可能产生相同的可达关系和相同的偏序。例如，有向无环图具有两条边，并且与具有三条边、和的图具有相同的可达性关系。这两种 DAGS 产生相同的偏序，其中顶点的顺序为。
[[File:Hasse diagram of powerset of 3.svg|thumb|300px|A [[Hasse diagram]] representing the partial order of set inclusion (⊆) among the subsets of a three-element set.]]
A [[Hasse diagram representing the partial order of set inclusion (⊆) among the subsets of a three-element set.]]
[[ Hasse 图表示三元素集合子集中集合包含(something)的偏序]]
If {{mvar|G}} is a DAG, its [[transitive closure]] is the graph with the most edges that represents the same reachability relation. It has an edge {{math|''u'' → ''v''}} whenever {{mvar|u}} can reach {{mvar|v}}. That is, it has an edge for every related pair {{math|''u'' ≤ ''v''}} of distinct elements in the reachability relation of {{mvar|G}}, and may therefore be thought of as a direct translation of the reachability relation {{math|≤}} into graph-theoretic terms. The same method of translating partial orders into DAGs works more generally: for every finite partially ordered set {{math|(''S'', ≤)}}, the graph that has a vertex for each member of {{mvar|S}} and an edge for each pair of elements related by {{math|''u'' ≤ ''v''}} is automatically a transitively closed DAG, and has {{math|(''S'', ≤)}} as its reachability relation. In this way, every finite partially ordered set can be represented as the reachability relation of a DAG.
If is a DAG, its transitive closure is the graph with the most edges that represents the same reachability relation. It has an edge whenever can reach . That is, it has an edge for every related pair of distinct elements in the reachability relation of , 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 each member of and an edge for each pair of elements related by is automatically a transitively closed DAG, and has as its reachability relation. In this way, every finite partially ordered set can be represented as the reachability relation of a DAG.
如果是一个有向无环图，那么它的有向无环传递闭包图就是具有最多边的图，这些边表示相同的可达性关系。它有一个优势，无论何时可以达到。也就是说，可达关系中每一对相关的不同元素都有一个边，因此可以认为是可达关系直接转化为图论术语。同样的将偏序转换为 DAGs 的方法更为普遍: 对于每个有限偏序集，每个成员有一个顶点，每对相关元素有一条边的图是自动传递闭的 DAG，并且具有可达关系。这样，每个有限偏序集都可以表示为一个 DAG 的可达关系。
The [[transitive reduction]] of a DAG {{mvar|G}} is the graph with the fewest edges that represents the same reachability relation as {{mvar|G}}. It is a subgraph of {{mvar|G}}, formed by discarding the edges {{math|''u'' → ''v''}} for which {{mvar|G}} also contains a longer path connecting the same two vertices.
The transitive reduction of a DAG is the graph with the fewest edges that represents the same reachability relation as . It is a subgraph of , formed by discarding the edges for which also contains a longer path connecting the same two vertices.
有向无环图的传递约简是一个具有最少边的图，它表示的可达性关系与。这是一个子图的，由丢弃的边，其中也包含一个较长的路径连接相同的两个顶点。
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.<ref>{{citation|title=Digraphs: Theory, Algorithms and Applications|series=Springer Monographs in Mathematics|first1=Jørgen|last1=Bang-Jensen|first2=Gregory Z.|last2=Gutin|publisher=Springer|year=2008|isbn=978-1-84800-998-1|url=https://books.google.com/books?id=4UY-ucucWucC&pg=PA36|contribution=2.3 Transitive Digraphs, Transitive Closures and Reductions|pages=36–39}}.</ref>
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.
和传递闭包一样，传递约简也是针对 DAGs 的唯一定义。相反，对于不是无圈的有向图，可以有多个具有相同可达关系的极小子图。
If a DAG {{mvar|G}} has a reachability relation described by the partial order {{math|≤}}, then the transitive reduction of {{mvar|G}} is a subgraph of {{mvar|G}} that has an edge {{math|''u'' → ''v''}} for every pair in the [[covering relation]] of {{math|≤}}. 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 drawing]]s. A [[Hasse diagram]] of a partial order is a drawing of the transitive reduction in which the orientation of each edge is shown by placing the starting vertex of the edge in a lower position than its ending vertex.<ref>{{citation|title=Graphs, Networks and Algorithms|volume=5|series=Algorithms and Computation in Mathematics|first=Dieter|last=Jungnickel|publisher=Springer|year=2012|isbn=978-3-642-32278-5|pages=92–93|url=https://books.google.com/books?id=PrXxFHmchwcC&pg=PA92}}.</ref>
If a DAG has a reachability relation described by the partial order , then the transitive reduction of is a subgraph of that has an edge for every pair in the covering relation of . 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 each edge is shown by placing the starting vertex of the edge in a lower position than its ending vertex.
如果一个有向无环图具有一个由偏序描述的可达关系，那么它的传递约简就是一个子图，该子图的覆盖关系中的每一对都有一个边。传递约简在可视化它们所表示的部分顺序方面很有用，因为它们比其他表示相同顺序的图有更少的边，从而导致更简单的图绘制。偏序哈斯图是一幅传递归约图，其中每条边的方向通过将边的起始顶点放置在比其终止顶点位置更低的位置来显示。
=== Topological ordering ===
{{multiple image|image1=Topological Ordering.svg|caption1=A [[Topological sorting|topological ordering]] of a directed acyclic graph: every [[Edge (graph theory)|edge]] goes from earlier in the ordering (upper left) to later in the ordering (lower right). A directed graph is acyclic if and only if it has a topological ordering.|image2=Transitive Closure.svg|caption2=Adding the red edges to the blue directed acyclic graph produces another DAG, the [[transitive closure]] of the blue graph. For each red or blue edge {{mvar|uv}}, {{mvar|v}} is [[Reachability|reachable]] from {{mvar|u}}: there exists a blue path starting at {{mvar|u}} and ending at {{mvar|v}}.}}
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.<ref name="bang"/>
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.<ref>{{citation|title=Algorithms|first1=Robert|last1=Sedgewick|author1-link=Robert Sedgewick (computer scientist)|first2=Kevin|last2=Wayne|edition=4th|publisher=Addison-Wesley|year=2011|isbn=978-0-13-276256-4|url=https://books.google.com/books?id=idUdqdDXqnAC&pg=PA598|pages=598–599|contribution=4,2,25 Unique topological ordering}}.</ref>
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.
有向无环图的拓扑序族与有向无环图的可达关系的线性扩张族相同，因此任意两个表示相同偏序的图具有相同的拓扑序集。
The family of topological orderings of a DAG is the same as the family of [[linear extension]]s of the reachability relation for the DAG,<ref>{{citation|title=A Short Course in Discrete Mathematics|series=Dover Books on Computer Science|first1=Edward A.|last1=Bender|first2=S. Gill|last2=Williamson|publisher=Courier Dover Publications|year=2005|isbn=978-0-486-43946-4|page=142|url=https://books.google.com/books?id=iuEoAwAAQBAJ&pg=PA142|contribution=Example 26 (Linear extensions – topological sorts)}}.</ref> so any two graphs representing the same partial order have the same set of topological orders.
=== Combinatorial enumeration ===
The graph enumeration problem of counting directed acyclic graphs was studied by .
研究了计数有向无圈图的图计数问题。
The [[graph enumeration]] problem of counting directed acyclic graphs was studied by {{harvtxt|Robinson|1973}}.<ref name="enum">{{citation|first=R. W.|last=Robinson|contribution=Counting labeled acyclic digraphs|pages=239–273|editor-first=F.|editor-last=Harary|editor-link=Frank Harary|title=New Directions in the Theory of Graphs|publisher=Academic Press|year=1973}}. See also {{citation
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
在有标记的顶点上的 DAGs 数量为(对这些数字在有向无环图的拓扑顺序中出现的顺序没有限制)
|last1 = Harary | first1 = Frank | author1-link = Frank Harary | first2 = Edgar M. | last2 = Palmer | year = 1973| title = Graphical Enumeration | publisher = [[Academic Press]] | isbn = 978-0-12-324245-7 | page=19}}.</ref>
1, 1, 3, 25, 543, 29281, 3781503, … .
1, 1, 3, 25, 543, 29281, 3781503, … .
The number of DAGs on {{mvar|n}} labeled vertices, for {{math|1=''n'' = 0, 1, 2, 3, …}} (without restrictions on the order in which these numbers appear in a topological ordering of the DAG) is
These numbers may be computed by the recurrence relation
这些数字可能是由美国递回关系式计算出来的
:1, 1, 3, 25, 543, 29281, 3781503, … {{OEIS|id=A003024}}.
<math>a_n = \sum_{k=1}^n (-1)^{k-1} {n\choose k}2^{k(n-k)} a_{n-k}.</math> 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.
< math > a _ n = sum _ { k = 1} ^ n (- 1) ^ { k-1}{ n choose k }2 ^ { k (n-k)} a { n-k }.证明了同一个数可以计算所有特征值为正实数的(0,1)矩阵。证明是双射的: 一个矩阵是一个 DAG 的邻接矩阵当且仅当它是一个所有特征值为正的矩阵，其中表示单位矩阵。因为一个 DAG 不能有自循环，所以它的邻接矩阵必须有一个零对角线，所以加上这一点保留了所有矩阵系数都是0或1的性质。
These numbers may be computed by the [[recurrence relation]]
:<math>a_n = \sum_{k=1}^n (-1)^{k-1} {n\choose k}2^{k(n-k)} a_{n-k}.</math><ref name="enum" />
[[Eric W. Weisstein]] conjectured,<ref>{{MathWorld | urlname=WeissteinsConjecture | title=Weisstein's Conjecture|mode=cs2}}</ref> and {{harvtxt|McKay|Royle|Wanless|Oggier|2004}} proved, that the same numbers count the [[Logical matrix|(0,1) matrices]] for which all [[eigenvalue]]s are positive [[real number]]s. The proof is [[bijective proof|bijective]]: a matrix {{mvar|A}} is an [[adjacency matrix]] of a DAG if and only if {{math|''A'' + ''I''}} is a (0,1) matrix with all eigenvalues positive, where {{mvar|I}} denotes the [[identity matrix]]. Because a DAG cannot have [[Loop (graph theory)|self-loops]], its adjacency matrix must have a zero diagonal, so adding {{mvar|I}} preserves the property that all matrix coefficients are 0 or 1.<ref>{{citation|last1=McKay|first1=B. D.|author1-link=Brendan McKay|last2=Royle|first2=G. F.|author2-link=Gordon Royle|last3=Wanless|first3=I. M.|last4=Oggier|first4=F. E.|author4-link= Frédérique Oggier |last5=Sloane|first5=N. J. A.|author5-link= Neil Sloane|last6=Wilf|first6=H.|author6-link=Herbert Wilf|title=Acyclic digraphs and eigenvalues of (0,1)-matrices|journal=[[Journal of Integer Sequences]]|volume=7|year=2004|url=http://www.cs.uwaterloo.ca/journals/JIS/VOL7/Sloane/sloane15.html}}, Article 04.3.3.</ref>
{{multiple image
{多重图像
|image1=Polytree.svg|caption1=A polytree, a DAG formed by orienting the edges of an undirected tree
1 = Polytree.svg | caption1 = 一个多边形树，一个有向无向树的边缘定向形成的 DAG
=== Related families of graphs ===
|image2=Butterfly multitree.svg|caption2=A multitree, A DAG in which each subgraph reachable from a single vertex (red) is a tree
| image2 = Butterfly multitree.svg | caption2 = 一个多树，一个 DAG，其中每个从单个顶点(红色)可到达的子图是一棵树
{{multiple image
|width2=254<!---adjust to make both images the same height-->
| width2 = 254 < !-调整使两个图像的高度相同
|image1=Polytree.svg|caption1=A [[polytree]], a DAG formed by [[Orientation (graph theory)|orienting]] the edges of an undirected tree
}}
}}
|image2=Butterfly multitree.svg|caption2=A [[multitree]], A DAG in which each subgraph reachable from a single vertex (red) is a tree
A polytree is a directed graph formed by orienting the edges of a free tree. Every polytree is a DAG. In particular, this is true of the arborescences formed by directing all edges outwards from the roots of a tree.
一个多边形是一个有向图形成的定向的边自由树。每棵多叶树都是一个 DAG。特别是，这是真正的树枝形成的所有边缘向外从树根。
|width2=254<!---adjust to make both images the same height-->
}}
A multitree (also called a strongly unambiguous graph or a mangrove) is a directed graph in which there is at most one directed path (in either direction) between any two vertices; equivalently, it is a DAG in which, for every vertex , the subgraph reachable from forms a tree.
多重树(也称为强无歧义图或红树)是一个有向图，其中任意两个顶点之间至多有一条有向路(任意方向) ; 等价地，它是一个有向无环图，其中对于每个顶点，从该子图可达到的子图形成一棵树。
A [[polytree]] is a directed graph formed by orienting the edges of a [[tree (graph theory)|free tree]].<ref>{{citation
| last1 = Rebane
| first1 = George
| last2 = Pearl
| first2 = Judea
| author2-link = Judea Pearl
Topological sorting is the algorithmic problem of finding a topological ordering of a given DAG. It can be solved in linear time. 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. or alternatively, for some topological sorting algorithms, by verifying that the algorithm successfully orders all the vertices without meeting an error condition.
拓扑排序是寻找给定 DAG 的拓扑顺序的计算问题。它可以在线性时间内求解。的拓扑排序算法直接建立顶点排序。它维护了一个顶点列表，这些顶点没有来自其他没有被部分构造的拓扑顺序包括在内的顶点的入射边; 最初这个列表由没有入射边的顶点组成。然后，它重复地从这个列表中添加一个顶点到部分构造的拓扑排序的末尾，并检查它的邻居是否应该添加到这个列表中。当所有顶点都以这种方式被处理时，算法终止。或者，对于某些拓扑排序算法，通过验证算法成功地排序所有顶点，而不满足错误条件。
| contribution = The recovery of causal poly-trees from statistical data
| pages = 222–228
| title = in Proc. 3rd Annual Conference on Uncertainty in Artificial Intelligence (UAI 1987), Seattle, WA, USA, July 1987
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 χ(−1)}}, where is the chromatic polynomial of the given graph.
任何无向图都可以通过为其顶点选择一个总的顺序，并按顺序将前一个端点的每条边定向到后一个端点，从而构成一个 DAG。所得到的边的方向称为无圈方向。不同的总序可能导致相同的无圈取向，因此一个顶点图可以有少于个无圈取向。非循环取向的个数等于 χ (- 1)} ，其中是给定图的色多项式。
| url = ftp://ftp.cs.ucla.edu/tech-report/198_-reports/870031.pdf
| year = 1987
condensation of the blue directed graph. It is formed by contracting each strongly connected component of the blue graph into a single yellow vertex.]]
蓝色有向图的凝聚。它是由蓝色图的每个强连通分量收缩成一个黄色顶点形成的。]
}}{{Dead link|date=July 2019 |bot=InternetArchiveBot |fix-attempted=yes }}.</ref> Every polytree is a DAG. In particular, this is true of the [[Arborescence (graph theory)|arborescences]] formed by directing all edges outwards from the roots of a tree.
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.
任何有向图都可以通过删除一个反馈顶点集或一个反馈弧集、一组顶点或边(分别)来构成一个有向无环图。然而，最小的这样的集合是 np 难以找到。一个任意的有向图也可以通过将每个强连通分量收缩到一个单独的超顶点而转化为 DAG，称为它的凝聚。当图是非循环的时候，它的最小反馈顶点集和反馈弧集是空的，它的缩聚就是图本身。
A [[multitree]] (also called a strongly unambiguous graph or a mangrove) is a directed graph in which there is at most one directed path (in either direction) between any two vertices; equivalently, it is a DAG in which, for every vertex {{mvar|v}}, the subgraph reachable from {{mvar|v}} forms a tree.<ref>{{citation
| last1 = Furnas | first1 = George W. | author1-link = George Furnas
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. 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.
一个给定的有向无环图的传递闭包，包括顶点和边，可以通过使用广度优先搜索或深度优先搜索来测试每个顶点的可达性来及时构造。或者，它可以及时解决在哪里是矩阵乘法算法的指数; 这是一个理论上的改进超过了稠密图的界。
| last2 = Zacks | first2 = Jeff
| contribution = Multitrees: enriching and reusing hierarchical structure
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.
在所有这些传递闭包算法中，可以区分至少一条长度为2条或更多的路径可到达的顶点对和只能通过一条长度为1条路径连接的顶点对。传递约简由形成长度的边组成——一条路径是连接其端点的唯一路径。因此，传递约简可以在与传递闭包相同的渐近时间范围内构造。
| doi = 10.1145/191666.191778
| pages = 330–336
| title = Proc. SIGCHI conference on Human Factors in Computing Systems (CHI '94)
| year = 1994| isbn = 978-0897916509 | s2cid = 18710118 }}.</ref>
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.
闭包问题以一个顶点加权有向无环图为输入，寻求一个闭包的最小(或最大)权重-一组顶点 c，这样没有边离开 c。这个问题可以在没有无环性假设的情况下表示为有向图，但没有更大的一般性，因为在这种情况下，它等价于图的凝聚上的同样问题。通过对最大流问题的约简，可以在多项式时间内求解。
== Computational problems ==
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. In contrast, for arbitrary graphs the shortest path may require slower algorithms such as Dijkstra's algorithm or the Bellman–Ford algorithm, and longest paths in arbitrary graphs are NP-hard to find.
基于拓扑排序原理，有些算法用在 DAGs 上代替一般图时变得更简单。例如，通过处理拓扑有序中的顶点，并计算每个顶点的路径长度为通过任一传入边得到的最小或最大长度，可以在线性时间内从给定的 DAGs 顶点找到最短路径和最长路径。相反，对于任意图，最短路径可能需要较慢的算法，如 Dijkstra 算法或 Bellman-Ford 算法，而任意图中的最长路径是 np 难以找到的。
=== Topological sorting and recognition ===
{{Main|Topological sorting}}
[[Topological sorting]] is the algorithmic problem of finding a topological ordering of a given DAG. It can be solved in [[linear time]].<ref name="clrs">{{Introduction to Algorithms|edition=2|mode=cs2}} Section 22.4, Topological sort, pp. 549–552.</ref> 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.<ref name="j50" /> Alternatively, a topological ordering may be constructed by reversing a [[postorder]] numbering of a [[depth-first search]] graph traversal.<ref name="clrs" />
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 valid<ref>For [[depth-first search]] based topological sorting algorithm, this validity check can be interleaved with the topological sorting algorithm itself; see e.g. {{citation|title=The Algorithm Design Manual|first=Steven S.|last=Skiena|publisher=Springer|year=2009|isbn=978-1-84800-070-4|pages=179–181|url=https://books.google.com/books?id=7XUSn0IKQEgC&pg=PA179}}.</ref> or alternatively, for some topological sorting algorithms, by verifying that the algorithm successfully orders all the vertices without meeting an error condition.<ref name="j50">{{harvtxt|Jungnickel|2012}}, pp. 50–51.</ref>
Directed acyclic graphs representations of partial orderings have many applications in scheduling for systems of tasks with ordering constraints.
偏序的有向无圈图表示在有序约束的任务系统的调度中有许多应用。
An important class of problems of this type concern collections of objects that need to be updated, such as the cells of a spreadsheet after one of the cells has been changed, or the object files of a piece of computer software after its source code has been changed.
这种类型的一类重要问题涉及需要更新的对象集合，例如电子表格中某个单元格更改后的单元格，或者计算机软件中某个源代码更改后的目标文件。
=== Construction from cyclic graphs ===
In this context, a dependency graph is a graph that has a vertex for each object to be updated, and an edge connecting two objects whenever one of them needs to be updated earlier than the other. A cycle in this graph is called a circular dependency, and is generally not allowed, because there would be no way to consistently schedule the tasks involved in the cycle.
在此上下文中，依赖关系图是一个图，其中每个要更新的对象都有一个顶点，并且每当其中一个对象需要比另一个更早更新时，就有一条连接两个对象的边。这个图中的循环称为循环依赖，通常不允许这样做，因为没有办法始终如一地安排循环中涉及的任务。
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 (graph theory)|orientation]] of the edges is called an [[acyclic orientation]]. Different total orders may lead to the same acyclic orientation, so an {{mvar|n}}-vertex graph can have fewer than {{math|''n''!}} acyclic orientations. The number of acyclic orientations is equal to {{math|{{!}}''χ''(−1){{!}}}}, where {{mvar|χ}} is the [[chromatic polynomial]] of the given graph.<ref>{{citation|first=Richard P.|last=Stanley|author-link=Richard P. Stanley|title=Acyclic orientations of graphs|journal=Discrete Mathematics|volume=5|issue=2 |pages=171–178|year= 1973|doi=10.1016/0012-365X(73)90108-8|url=http://math.mit.edu/~rstan/pubs/pubfiles/18.pdf}}.</ref>
Dependency graphs without circular dependencies form DAGs.
无循环依赖关系的依赖图形成 DAGs。
[[File:Graph Condensation.svg|thumb|upright=1.5|The yellow directed acyclic graph is the [[Condensation (graph theory)|condensation]] of the blue directed graph. It is formed by [[Edge contraction|contracting]] each [[strongly connected component]] of the blue graph into a single yellow vertex.]]
For instance, when one cell of a spreadsheet changes, it is necessary to recalculate the values of other cells that depend directly or indirectly on the changed cell. For this problem, the tasks to be scheduled are the recalculations of the values of individual cells of the spreadsheet. Dependencies arise when an expression in one cell uses a value from another cell. In such a case, the value that is used must be recalculated earlier than the expression that uses it. Topologically ordering the dependency graph, and using this topological order to schedule the cell updates, allows the whole spreadsheet to be updated with only a single evaluation per cell. Similar problems of task ordering arise in makefiles for program compilation
例如，当电子表格的一个单元格发生更改时，必须重新计算直接或间接依赖于更改单元格的其他单元格的值。对于此问题，计划中的任务是对电子表格各单元格的值重新计算。当一个单元格中的表达式使用另一个单元格中的值时，就会出现依赖性。在这种情况下，必须比使用该值的表达式更早地重新计算使用的值。通过拓扑排序依赖关系图，并使用这个拓扑有序表来安排单元格的更新，可以使整个电子表格只需要对每个单元格进行一次计算就可以更新。类似的任务排序问题也出现在程序编译的 makefile 中
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.<ref>{{Garey-Johnson}}, Problems GT7 and GT8, pp. 191–192.</ref> An arbitrary directed graph may also be transformed into a DAG, called its [[condensation (graph theory)|condensation]], by [[Edge contraction|contracting]] each of its [[strongly connected component]]s into a single supervertex.<ref>{{citation|title=Structural Models: An Introduction to the Theory of Directed Graphs|last1=Harary|first1=Frank|author1-link=Frank Harary|last2=Norman|first2=Robert Z.|last3=Cartwright|first3=Dorwin|publisher=John Wiley & Sons|year=1965|page=63}}.</ref> When the graph is already acyclic, its smallest feedback vertex sets and feedback arc sets are [[empty set|empty]], and its condensation is the graph itself.
PERT chart for a project with five milestones (labeled 10–50) and six tasks (labeled A–F). There are two critical paths, ADF and BC.
有五个里程碑(标记为10-50)和六个任务(标记为 a-f)的项目的 PERT 图表。有两条关键路径，ADF 和 BC。
=== Transitive closure and transitive reduction ===
A somewhat different DAG-based formulation of scheduling constraints is used by the program evaluation and review technique (PERT), a method for management of large human projects that was one of the first applications of DAGs. In this method, the vertices of a DAG represent milestones of a project rather than specific tasks to be performed. Instead, a task or activity is represented by an edge of a DAG, connecting two milestones that mark the beginning and completion of the task. Each such edge is labeled with an estimate for the amount of time that it will take a team of workers to perform the task. The longest path in this DAG represents the critical path of the project, the one that controls the total time for the project. Individual milestones can be scheduled according to the lengths of the longest paths ending at their vertices.
计划评审技术(program evaluation and review technique，PERT)使用了一种略有不同的基于 DAGs 的进度约束形式，这种方法是 DAGs 的首批应用之一，用于管理大型人类项目。在这种方法中，DAG 的顶点代表项目的里程碑，而不是要执行的具体任务。相反，一个任务或活动由一个有向无环图的边缘表示，连接两个标志任务开始和完成的里程碑。每个这样的边都标注了一个估计值，表示一组工作人员执行该任务所需的时间。DAG 中最长的路径代表项目的关键路径，它控制项目的总时间。单个里程碑可以根据在其顶点结束的最长路径的长度进行调度。
The transitive closure of a given DAG, with {{mvar|n}} vertices and {{mvar|m}} edges, may be constructed in time {{math|''O''(''mn'')}} by using either [[breadth-first search]] or [[depth-first search]] to test reachability from each vertex.<ref>{{harvtxt|Skiena|2009}}, p. 495.</ref> Alternatively, it can be solved in time {{math|''O''(''n''<sup>''ω''</sup>)}} where {{math|''ω'' < 2.373}} is the [[Computational complexity of matrix multiplication#Matrix multiplication exponent|exponent for matrix multiplication algorithms]]; this is a theoretical improvement over the {{math|''O''(''mn'')}} bound for [[dense graph]]s.<ref>{{harvtxt|Skiena|2009}}, p. 496.</ref>
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.<ref>{{harvtxt|Bang-Jensen|Gutin|2008}}, p. 38.</ref>
A directed acyclic graph may be used to represent a network of processing elements. In this representation, data enters a processing element through its incoming edges and leaves the element through its outgoing edges.
有向无环图可以用来表示处理元素的网络。在这种表示法中，数据通过传入边进入处理元素，通过传出边离开元素。
=== Closure problem ===
For instance, in electronic circuit design, static combinational logic blocks can be represented as an acyclic system of logic gates that computes a function of an input, where the input and output of the function are represented as individual bits. In general, the output of these blocks cannot be used as the input unless it is captured by a register or state element which maintains its acyclic properties. Electronic circuit schematics either on paper or in a database are a form of directed acyclic graphs using instances or components to form a directed reference to a lower level component. Electronic circuits themselves are not necessarily acyclic or directed.
例如，在电子电路设计中，静态组合逻辑电路块可以表示为一个逻辑门的非循环系统，计算一个输入函数，其中的输入和输出被表示为单独的位。一般来说，这些块的输出不能用作输入，除非它被保持其非循环属性的寄存器或状态元素捕获。纸上或数据库中的电子电路原理图是一种有向无环图的形式，使用实例或组件形成对较低级别组件的有向引用。电子电路本身不一定是无环或有向的。
{{Main|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]].<ref>{{citation
Dataflow programming languages describe systems of operations on data streams, and the connections between the outputs of some operations and the inputs of others. These languages can be convenient for describing repetitive data processing tasks, in which the same acyclically-connected collection of operations is applied to many data items. They can be executed as a parallel algorithm in which each operation is performed by a parallel process as soon as another set of inputs becomes available to it.
数据流编程语言描述了对数据流的操作系统，以及某些操作的输出和其他操作的输入之间的连接。这些语言可以方便地描述重复的数据处理任务，在这些任务中，对许多数据项应用相同的无环连接的操作集合。它们可以作为一个并行算法执行，其中每个操作在另一组输入可用时由一个并行进程执行。
| last = Picard | first = Jean-Claude
| doi = 10.1287/mnsc.22.11.1268
In compilers, straight line code (that is, sequences of statements without loops or conditional branches) may be represented by a DAG describing the inputs and outputs of each of the arithmetic operations performed within the code. This representation allows the compiler to perform common subexpression elimination efficiently. At a higher level of code organization, the acyclic dependencies principle states that the dependencies between modules or components of a large software system should form a directed acyclic graph.
在编译器中，直线代码(即没有循环或条件分支的语句序列)可以由 DAG 表示，DAG 描述代码中执行的每个算术运算的输入和输出。此表示形式允许编译器有效地执行公共子表达式消除。在更高层次的代码组织中，非循环依赖原则指出，大型软件系统的模块或组件之间的依赖应该形成一个有向无环图。
| issue = 11
| journal = [[Management Science (journal)|Management Science]]
Feedforward neural networks are another example.
前馈神经网络是另一个例子。
| mr = 0403596
| pages = 1268–1272
| title = Maximal closure of a graph and applications to combinatorial problems
| volume = 22
Graphs in which vertices represent events occurring at a definite time, and where the edges are always point from the early time vertex to a late time vertex of the edge, are necessarily directed and acyclic. The lack of a cycle follows because the time associated with a vertex always increases as you follow any path in the graph so you can never return to a vertex on a path. This reflects our natural intuition that causality means events can only affect the future, they never affect the past, and thus we have no causal loops. An example of this type of directed acyclic graph are those encountered in the causal set approach to quantum gravity though in this case the graphs considered are transitively complete. In the version history example, each version of the software is associated with a unique time, typically the time the version was saved, committed or released. For citation graphs, the documents are published at one time and can only refer to older documents.
顶点表示在一定时间内发生的事件，并且边始终是从边的早期时间顶点到后期时间顶点的点的图，必然是有向的和无环的。没有循环是因为当你沿着图中的任何一条路径走时，与一个顶点相关的时间总是增加，所以你永远不能返回到路径上的一个顶点。这反映了我们的自然直觉，因果关系意味着事件只能影响未来，它们从不影响过去，因此我们没有因果循环。这类有向无环图的一个例子是在量子引力的因果集方法中遇到的，尽管在这种情况下所考虑的图是传递完全的。在版本历史示例中，软件的每个版本都与一个唯一的时间相关联，通常是保存、提交或发布版本的时间。对于引用图，这些文献只能发表一次，并且只能引用较早的文献。
| year = 1976}}.</ref>
Sometimes events are not associated with a specific physical time. Provided that pairs of events have a purely causal relationship, that is edges represent causal relations between the events, we will have a directed acyclic graph. For instance, a Bayesian network represents a system of probabilistic events as vertices in a directed acyclic graph, in which the likelihood of an event may be calculated from the likelihoods of its predecessors in the DAG. In this context, the moral graph of a DAG is the undirected graph created by adding an (undirected) edge between all parents of the same vertex (sometimes called marrying), and then replacing all directed edges by undirected edges. Another type of graph with a similar causal structure is an influence diagram, the vertices of which represent either decisions to be made or unknown information, and the edges of which represent causal influences from one vertex to another. In epidemiology, for instance, these diagrams are often used to estimate the expected value of different choices for intervention.
有时，事件与特定的物理时间无关。如果成对的事件具有纯粹的因果关系，即边缘代表事件之间的因果关系，那么我们就有了一个有向无环图。例如，一个贝氏网路代表一个概率事件系统作为一个有向无环图中的顶点，在这个顶点中，一个事件的可能性可以通过它在 DAG 中的前身的可能性来计算。在这种情况下，有向无环图是在同一顶点的所有父母之间加上一条(无向)边(有时称为结合) ，然后用无向边代替所有有向边而产生的无向图。另一种具有类似因果结构的图类型是影响图，其顶点表示要作出的决定或未知信息，其边表示从一个顶点到另一个顶点的因果影响。例如，在流行病学中，这些图表通常用于估计不同干预选择的期望值。
=== 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 path]]s and [[longest path problem|longest paths]] from a given starting vertex in DAGs in linear time by [[Topological sorting#Application to shortest path finding|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.<ref>Cormen et al. 2001, Section 24.2, Single-source shortest paths in directed acyclic graphs, pp. 592–595.</ref> In contrast, for arbitrary graphs the shortest path may require slower algorithms such as [[Dijkstra's algorithm]] or the [[Bellman–Ford algorithm]],<ref>Cormen et al. 2001, Sections 24.1, The Bellman–Ford algorithm, pp. 588–592, and 24.3, Dijkstra's algorithm, pp. 595–601.</ref> and longest paths in arbitrary graphs are [[NP-hard]] to find.<ref>Cormen et al. 2001, p. 966.</ref>
The converse is also true. That is in any application represented by a directed acyclic graph there is a causal structure, either an explicit order or time in the example or an order which can be derived from graph structure. This follows because all directed acyclic graphs have a topological ordering, i.e. there is at least one way to put the vertices in an order such that all edges point in the same direction along that order.
反之亦然。也就是说，在任何用有向无环图表示的应用程序中，都存在一个因果结构，要么是例子中显式的顺序或时间，要么是可以从图结构中派生出来的顺序。这是因为所有有向无圈图都有一个拓扑序，即。至少有一种方法可以将顶点按顺序排列，使所有边沿着这个顺序指向同一个方向。
== Applications ==
Family tree of the [[Ptolemaic dynasty, with many marriages between close relatives causing pedigree collapse]]
托勒密王朝的家谱，许多近亲之间的婚姻导致家谱崩溃
=== Scheduling ===
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" relationships between women) and patrilineal descent ("father" relationships between men) are trees within this graph. Because
家族树可以看作是有向无圈图，每个家族成员有一个顶点，每个亲子关系有一条边。除了名字，这些图并不一定是树，因为亲戚之间的婚姻(所以一个孩子在母亲和父亲方面有一个共同的祖先)会导致家谱崩溃。母系血统(女性之间的“母亲”关系)和父系血统(男性之间的“父亲”关系)的图表就是这个图表中的树。因为
Directed acyclic graphs representations of partial orderings have many applications in [[Schedule|scheduling]] for systems of tasks with ordering constraints.<ref>{{harvtxt|Skiena|2009}}, p. 469.</ref>
no one can become their own ancestor, family trees are acyclic.
没有人能成为自己的祖先，家谱是无环的。
An important class of problems of this type concern collections of objects that need to be updated, such as the cells of a [[spreadsheet]] after one of the cells has been changed, or the [[object file]]s of a piece of computer software after its [[source code]] has been changed.
In this context, a [[dependency graph]] is a graph that has a vertex for each object to be updated, and an edge connecting two objects whenever one of them needs to be updated earlier than the other. A cycle in this graph is called a [[circular dependency]], and is generally not allowed, because there would be no way to consistently schedule the tasks involved in the cycle.
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.
分散式版本控制版本的历史，比如 Git，通常有一个有向无环图版本的结构，每个版本都有一个顶点，一条边连接直接从其他版本派生出来的修订对。由于合并，这些通常不是树。
Dependency graphs without circular dependencies form DAGs.<ref>{{citation | last1=Al-Mutawa | first1=H. A. | last2=Dietrich | first2=J. | last3=Marsland | first3=S. | last4=McCartin | first4=C. | contribution=On the shape of circular dependencies in Java programs | doi=10.1109/ASWEC.2014.15 | pages=48–57 | publisher=IEEE | title=23rd Australian Software Engineering Conference | year=2014| isbn=978-1-4799-3149-1 | s2cid=17570052 }}.</ref>
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 .
在计算几何的许多随机算法中，该算法维护一个历史 DAG，它表示一个几何结构在一系列结构变化过程中的版本历史。例如，在一个随机增量的三角形算法中，每增加一个点，三角形就被三个更小的三角形替换，或者用一对不同的三角形“翻转”操作替换成对的三角形，从而改变了三角形德劳内三角化。该算法的历史 DAG 包含每个三角形的顶点，以及每个三角形到其他两三个三角形的边。这种结构允许有效地回答点位置查询: 要在德劳内三角化中找到查询点的位置，按照历史 DAG 中的路径，在每一步移动到包含的替换三角形。在这条路径中达到的最后一个三角形必须是包含。
For instance, when one cell of a [[spreadsheet]] changes, it is necessary to recalculate the values of other cells that depend directly or indirectly on the changed cell. For this problem, the tasks to be scheduled are the recalculations of the values of individual cells of the spreadsheet. Dependencies arise when an expression in one cell uses a value from another cell. In such a case, the value that is used must be recalculated earlier than the expression that uses it. Topologically ordering the dependency graph, and using this topological order to schedule the cell updates, allows the whole spreadsheet to be updated with only a single evaluation per cell.<ref name="hgt1181">{{citation |title=Handbook of Graph Theory |first1=Jonathan L. |last1=Gross |first2=Jay |last2=Yellen |first3=Ping |last3=Zhang | author3-link = Ping Zhang (graph theorist)|edition=2nd |publisher=CRC Press |year=2013 |isbn=978-1-4398-8018-0 |page=1181 |url=https://books.google.com/books?id=cntcAgAAQBAJ&pg=PA1181}}.</ref> Similar problems of task ordering arise in [[makefile]]s for program compilation<ref name="hgt1181" /> and [[instruction scheduling]] for low-level computer program optimization.<ref>{{citation |title=The Compiler Design Handbook: Optimizations and Machine Code Generation |first1=Y. N. |last1=Srikant |first2=Priti |last2=Shankar |edition=2nd |publisher=CRC Press|year=2007 |isbn=978-1-4200-4383-9 |pages=19–39 |url=https://books.google.com/books?id=1kqAv-uDEPEC&pg=SA19-PA39}}.</ref>
[[File:Pert chart colored.svg|thumb|PERT chart for a project with five milestones (labeled 10–50) and six tasks (labeled A–F). There are two critical paths, ADF and BC.]]
In a citation graph the vertices are documents with a single publication date. The edges represent the citations from the bibliography of one document to other necessarily earlier documents. The classic example comes from the citations between academic papers as pointed out in the 1965 article "Networks of Scientific Papers" by Derek J. de Solla Price who went on to produce the first model of a citation network, the Price model. In this case the citation count of a paper is just the in-degree of the corresponding vertex of the citation network. This is an important measure in citation analysis. Court judgements provide another example as judges support their conclusions in one case by recalling other earlier decisions made in previous cases. A final example is provided by patents which must refer to earlier prior art, earlier patents which are relevant to the current patent claim. By taking the special properties of directed acyclic graphs into account, one can analyse citation networks with techniques not available when analysing the general graphs considered in many studies using network analysis. For instance transitive reduction gives a new insights into the citation distributions found in different applications highlighting clear differences in the mechanisms creating citations networks in different contexts. Another technique is main path analysis, which traces the citation links and suggests the most significant citation chains in a given citation graph.
在引用图中，顶点是只有一个出版日期的文档。边代表从一个文档的参考书目到其他必要的早期文档的引用。经典的例子来自于学术论文之间的引用，正如1965年德瑞克·约翰·德索拉·普莱斯在《科学论文网络》一文中指出的那样，他继续创造了引用网络的第一个模型---- 价格模型。在这种情况下，一篇论文的引文数量就是引文网络相应顶点的度数。这是21引文分析的一项重要措施。法院判决提供了另一个例子，因为法官通过回顾以前案件中作出的其他判决来支持他们在一个案件中的结论。最后一个例子是专利，必须提到先前的技术，先前的专利，这是有关当前的专利权利主张。通过考虑有向无环图的特殊性质，可以利用网络分析方法分析引文网络。例如，传递减法对不同应用中的引用分布提供了新的见解，突出了不同上下文中引用网络形成机制的明显差异。另一种技术是主路径分析，它跟踪引文链接，并提出给定引文图中最重要的引文链。
A somewhat different DAG-based formulation of scheduling constraints is used by the [[program evaluation and review technique]] (PERT), a method for management of large human projects that was one of the first applications of DAGs. In this method, the vertices of a DAG represent [[Milestone (project management)|milestones]] of a project rather than specific tasks to be performed. Instead, a task or activity is represented by an edge of a DAG, connecting two milestones that mark the beginning and completion of the task. Each such edge is labeled with an estimate for the amount of time that it will take a team of workers to perform the task. The [[Longest path problem|longest path]] in this DAG represents the [[Critical path method|critical path]] of the project, the one that controls the total time for the project. Individual milestones can be scheduled according to the lengths of the longest paths ending at their vertices.<ref>{{citation |title=What Every Engineer Should Know About Decision Making Under Uncertainty |first=John X. |last=Wang |publisher=CRC Press |year=2002 |isbn=978-0-8247-4373-4 |page=160 |url=https://books.google.com/books?id=C3yKML0dUVIC&pg=PA160}}.</ref>
The Price model is too simple to be a realistic model of a citation network but it is simple enough to allow for analytic solutions for some of its properties. Many of these can be found by using results derived from the undirected version of the Price model, the Barabási–Albert model. However, since Price's model gives a directed acyclic graph, it is a useful model when looking for analytic calculations of properties unique to directed acyclic graphs. For instance,
普莱斯模型过于简单，不可能成为引文网络的现实模型，但它足够简单，可以为其某些属性提供分析解。其中许多问题可以通过使用从价格模型(Barabási-Albert 模型)的无向版本得出的结果来找到。然而，由于 Price 的模型给出了一个有向无环图，所以在寻找有向无圈图所特有的性质的解析计算时，它是一个很有用的模型。比如说,
=== Data processing networks ===
the length of the longest path, from the n-th node added to the network to the first node in the network, scales as <math>\ln(n)</math>.
最长路径的长度，从添加到网络的第 n 个节点到网络中的第一个节点，缩放为 < math > ln (n) </math > 。
A directed acyclic graph may be used to represent a network of processing elements. In this representation, data enters a processing element through its incoming edges and leaves the element through its outgoing edges.
For instance, in electronic circuit design, static [[combinational logic]] blocks can be represented as an acyclic system of [[logic gate]]s that computes a function of an input, where the input and output of the function are represented as individual [[bit]]s. In general, the output of these blocks cannot be used as the input unless it is captured by a register or state element which maintains its acyclic properties.<ref>{{citation|title=Timing|first=Sachin|last=Sapatnekar|publisher=Springer|year=2004|isbn=978-1-4020-7671-8|page=133|url=https://books.google.com/books?id=fL9k-VkZVr0C&pg=PA133}}.</ref> Electronic circuit schematics either on paper or in a database are a form of directed acyclic graphs using instances or components to form a directed reference to a lower level component. Electronic circuits themselves are not necessarily acyclic or directed.
Directed acyclic graphs may also be used as a compact representation of a collection of sequences. In this type of application, one finds a DAG in which the paths form the given sequences. When many of the sequences share the same subsequences, these shared subsequences can be represented by a shared part of the DAG, allowing the representation to use less space than it would take to list out all of the sequences separately. For example, the directed acyclic word graph is a data structure in computer science formed by a directed acyclic graph with a single source and with edges labeled by letters or symbols; the paths from the source to the sinks in this graph represent a set of strings, such as English words. Any set of sequences can be represented as paths in a tree, by forming a tree vertex for every prefix of a sequence and making the parent of one of these vertices represent the sequence with one fewer element; the tree formed in this way for a set of strings is called a trie. A directed acyclic word graph saves space over a trie by allowing paths to diverge and rejoin, so that a set of words with the same possible suffixes can be represented by a single tree vertex.
有向无环图也可用作序列集合的紧凑表示。在这种类型的应用程序中，人们会找到一个 DAG，其中的路径形成给定的序列。当许多序列共享相同的子序列时，这些共享子序列可以由 DAG 的一个共享部分来表示，这使得这种表示比单独列出所有序列所需要的空间更少。例如，有向无环词图是计算机科学中的一种数据结构，由一个单源的有向无环图构成，其边缘用字母或符号标记; 在这个图中，从源到汇的路径表示一组字符串，例如英语单词。任何一组序列都可以表示为树中的路径，方法是为序列的每个前缀形成一个树顶点，并使其中一个顶点的父顶点表示只有一个元素的序列; 对于一组字符串以这种方式形成的树称为 trie。有向无环词图允许路径发散和重新连接，从而在一个三元图上节省空间，这样一组可能具有相同后缀的词可以由一个树顶点表示。
[[Dataflow programming]] languages describe systems of operations on [[data stream]]s, and the connections between the outputs of some operations and the inputs of others. These languages can be convenient for describing repetitive data processing tasks, in which the same acyclically-connected collection of operations is applied to many data items. They can be executed as a [[parallel algorithm]] in which each operation is performed by a parallel process as soon as another set of inputs becomes available to it.<ref>{{citation|title=Programming Symposium|series=Lecture Notes in Computer Science|volume=19|year=1974|pages=362–376|contribution=First version of a data flow procedure language|first=Jack B.|last=Dennis|doi=10.1007/3-540-06859-7_145|isbn=978-3-540-06859-4}}.</ref>
The same idea of using a DAG to represent a family of paths occurs in the binary decision diagram, a DAG-based data structure for representing binary functions. In a binary decision diagram, each non-sink vertex is labeled by the name of a binary variable, and each sink and each edge is labeled by a 0 or 1. The function value for any truth assignment to the variables is the value at the sink found by following a path, starting from the single source vertex, that at each non-sink vertex follows the outgoing edge labeled with the value of that vertex's variable. Just as directed acyclic word graphs can be viewed as a compressed form of , binary decision diagrams can be viewed as compressed forms of decision trees that save space by allowing paths to rejoin when they agree on the results of all remaining decisions.
使用 DAG 表示一系列路径的同样想法也出现在二元决策图中，这是一个基于 dags 的数据结构，用于表示二进制函数。在二元决策图中，每个无汇点都用一个二进制变量的名称标记，每个汇点和每条边都用一个0或1标记。任何对变量进行真值赋值的函数值，都是指从单个源顶点开始，沿着一条路径，在每个非汇顶点上沿着标有该顶点变量值的外向边缘，在汇处找到的值。正如有向无环字图可以看作是一种压缩形式，二叉决策图可以看作是一种压缩形式的决策树，通过允许路径在所有剩余决策的结果一致时重新连接来节省空间。
In [[compiler]]s, straight line code (that is, sequences of statements without loops or conditional branches) may be represented by a DAG describing the inputs and outputs of each of the arithmetic operations performed within the code. This representation allows the compiler to perform [[common subexpression elimination]] efficiently.<ref>{{citation|title=Advanced Backend Optimization|first1=Sid|last1=Touati|first2=Benoit|last2=de Dinechin|publisher=John Wiley & Sons|year=2014|isbn=978-1-118-64894-0|page=123|url=https://books.google.com/books?id=nO2-AwAAQBAJ&pg=PA123}}.</ref> At a higher level of code organization, the [[acyclic dependencies principle]] states that the dependencies between modules or components of a large software system should form a directed acyclic graph.<ref>{{citation|title=Large-Scale Software Architecture: A Practical Guide using UML|first1=Jeff|last1=Garland|first2=Richard|last2=Anthony|publisher=John Wiley & Sons|year=2003|isbn=9780470856383|page=215|url=https://books.google.com/books?id=_2oQLLSqZ88C&pg=PA215}}.</ref>
[[Feedforward neural network]]s are another example.
=== Causal structures ===
{{main|Bayesian network}}
Graphs in which vertices represent events occurring at a definite time, and where the edges are always point from the early time vertex to a late time vertex of the edge, are necessarily directed and acyclic. The lack of a cycle follows because the time associated with a vertex always increases as you follow any [[Path (graph theory)|path]] in the graph so you can never return to a vertex on a path. This reflects our natural intuition that causality means events can only affect the future, they never affect the past, and thus we have no [[causal loop]]s. An example of this type of directed acyclic graph are those encountered in the [[Causal sets|causal set approach to quantum gravity]] though in this case the graphs considered are [[#Transitive closure and transitive reduction|transitively complete]]. In the version history example, each version of the software is associated with a unique time, typically the time the version was saved, committed or released. For citation graphs, the documents are published at one time and can only refer to older documents.
Sometimes events are not associated with a specific physical time. Provided that pairs of events have a purely causal relationship, that is edges represent [[causality|causal relations]] between the events, we will have a directed acyclic graph.<ref>{{citation|title=Causal Learning|first1=Alison|last1=Gopnik|first2=Laura|last2=Schulz|publisher=Oxford University Press|year=2007|isbn=978-0-19-803928-0|page=4|url=https://books.google.com/books?id=35MKXlKoXIUC&pg=PA4}}.</ref> For instance, a [[Bayesian network]] represents a system of probabilistic events as vertices in a directed acyclic graph, in which the likelihood of an event may be calculated from the likelihoods of its predecessors in the DAG.<ref>{{citation|title=Probabilistic Boolean Networks: The Modeling and Control of Gene Regulatory Networks|publisher=Society for Industrial and Applied Mathematics|first1=Ilya|last1=Shmulevich|first2=Edward R.|last2=Dougherty|year=2010|isbn=978-0-89871-692-4|page=58|url=https://books.google.com/books?id=RfshqEgO7KgC&pg=PA58}}.</ref> In this context, the [[moral graph]] of a DAG is the undirected graph created by adding an (undirected) edge between all parents of the same vertex (sometimes called ''marrying''), and then replacing all directed edges by undirected edges.<ref>{{citation |last1= Cowell |first1= Robert G. |author2-link=Philip Dawid|last2=Dawid|first2=A. Philip|author3-link=Steffen Lauritzen|last3=Lauritzen|first3=Steffen L.|author4-link=David Spiegelhalter|last4=Spiegelhalter|first4=David J.|title= Probabilistic Networks and Expert Systems |publisher= Springer |year= 1999 |isbn= 978-0-387-98767-5 |chapter= 3.2.1 Moralization|pages= 31–33 }}.</ref> Another type of graph with a similar causal structure is an [[influence diagram]], the vertices of which represent either decisions to be made or unknown information, and the edges of which represent causal influences from one vertex to another.<ref>{{citation|title=The Technology Management Handbook|first=Richard C.|last=Dorf|publisher=CRC Press|year=1998|isbn=978-0-8493-8577-3|page=9{{hyphen}}7<!-- Do not conver this hyphen into a dash! It is a section-page number, not a range of page numbers. -->|url=https://books.google.com/books?id=C2u8I0DFo4IC&pg=SA9-PA7}}.</ref> In [[epidemiology]], for instance, these diagrams are often used to estimate the expected value of different choices for intervention.<ref>{{citation|title=Encyclopedia of Epidemiology, Volume 1|first=Sarah|last=Boslaugh|publisher=SAGE|year=2008|isbn=978-1-4129-2816-8|page=255|url=https://books.google.com/books?id=wObgnN3x14kC&pg=PA255}}.</ref><ref name="pearl:95">{{citation | last = Pearl | first = Judea | doi = 10.1093/biomet/82.4.669 | issue = 4 | journal = Biometrika | pages = 669–709 | title = Causal diagrams for empirical research | volume = 82 | year = 1995| url = https://escholarship.org/uc/item/6gv9n38c }}.</ref>
Category:Directed graphs
类别: 有向图
Category:Directed acyclic graphs
范畴: 有向无圈图
The converse is also true. That is in any application represented by a directed acyclic graph there is a causal structure, either an explicit order or time in the example or an order which can be derived from graph structure. This follows because all directed acyclic graphs have a [[#Topological ordering|topological ordering]], i.e. there is at least one way to put the vertices in an order such that all edges point in the same direction along that order.
de:Graph (Graphentheorie)#Teilgraphen.2C Wege und Zyklen
de:Graph (Graphentheorie)#Teilgraphen.2C Wege und Zyklen
<noinclude>
<small>This page was moved from [[wikipedia:en:Directed acyclic graph]]. Its edit history can be viewed at [[有向无环图/edithistory]]</small></noinclude>
[[Category:待整理页面]]