更改

|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>

|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, … .

<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}.</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的性质。

<math>a_n = \sum_{k=1}^n (-1)^{k-1} {n\choose k}2^{k(n-k)} a_{n-k}.</math>证明了同一个数可以计算所有特征值为正实数的(0,1)矩阵。证明是双射的: 一个矩阵是一个 DAG 的邻接矩阵当且仅当它是一个所有特征值为正的矩阵，其中表示单位矩阵。因为一个 DAG 不能有自循环，所以它的邻接矩阵必须有一个零对角线，所以加上这一点保留了所有矩阵系数都是0或1的性质。

These numbers may be computed by the [[recurrence relation]]

These numbers may be computed by the [[recurrence relation]]

[[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''&nbsp;+&nbsp;''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>

[[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''&nbsp;+&nbsp;''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>

=== Related families of graphs ===

=== Related families of graphs ===

{{multiple image

{{multiple image

 

|image1=Polytree.svg|caption1=A [[polytree]], a DAG formed by [[Orientation (graph theory)|orienting]] the edges of an undirected tree 一个多树，一个 DAG，其中每个从单个顶点(红色)可到达的子图是一棵树

|image2=Butterfly multitree.svg|caption2=A [[multitree]], A DAG in which each subgraph reachable from a single vertex (red) is a tree 一个多边形是一个有向图形成的定向的边自由树。每棵多叶树都是一个 DAG。特别是，这是真正的树枝形成的所有边缘向外从树根。

 

|width2=254<!---adjust to make both images the same height-->  

 

|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

 

 

一个多边形是一个有向图形成的定向的边自由树。每棵多叶树都是一个 DAG。特别是，这是真正的树枝形成的所有边缘向外从树根。

 

|width2=254<!---adjust to make both images the same height-->

 

}}

}}

多重树(也称为强无歧义图或红树)是一个有向图，其中任意两个顶点之间至多有一条有向路(任意方向) ; 等价地，它是一个有向无环图，其中对于每个顶点，从该子图可达到的子图形成一棵树。

多重树(也称为强无歧义图或红树)是一个有向图，其中任意两个顶点之间至多有一条有向路(任意方向) ; 等价地，它是一个有向无环图，其中对于每个顶点，从该子图可达到的子图形成一棵树。

A [[polytree]] is a directed graph formed by orienting the edges of a [[tree (graph theory)|free tree]].<ref>{{citation

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 | 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 | url = ftp://ftp.cs.ucla.edu/tech-report/198_-reports/870031.pdf | year = 1987 }}{{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.

 

| last1 = Rebane

| first1 = George

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 | last2 = Zacks | first2 = Jeff | contribution = Multitrees: enriching and reusing hierarchical structure | 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>

| first2 = Judea

== Computational problems ==

| author2-link = Judea Pearl

=== Topological sorting and recognition ===

Topological sorting is the algorithmic problem of finding a topological ordering of a given DAG. It can be solved in linear time. 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.

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 的拓扑顺序的计算问题。它可以在线性时间内求解。的拓扑排序算法直接建立顶点排序。它维护了一个顶点列表，这些顶点没有来自其他没有被部分构造的拓扑顺序包括在内的顶点的入射边; 最初这个列表由没有入射边的顶点组成。然后，它重复地从这个列表中添加一个顶点到部分构造的拓扑排序的末尾，并检查它的邻居是否应该添加到这个列表中。当所有顶点都以这种方式被处理时，算法终止。或者，对于某些拓扑排序算法，通过验证算法成功地排序所有顶点，而不满足错误条件。

拓扑排序是寻找给定 DAG 的拓扑顺序的计算问题。它可以在线性时间内求解。的拓扑排序算法直接建立顶点排序。它维护了一个顶点列表，这些顶点没有来自其他没有被部分构造的拓扑顺序包括在内的顶点的入射边; 最初这个列表由没有入射边的顶点组成。然后，它重复地从这个列表中添加一个顶点到部分构造的拓扑排序的末尾，并检查它的邻居是否应该添加到这个列表中。当所有顶点都以这种方式被处理时，算法终止。或者，对于某些拓扑排序算法，通过验证算法成功地排序所有顶点，而不满足错误条件。

| contribution = The recovery of causal poly-trees from statistical data

=== Construction from cyclic graphs ===

 

Any undirected graph may be made into a DAG by choosing a total order for its vertices and directing every edge from the earlier endpoint in the order to the later endpoint. The resulting orientation of the edges is called an acyclic orientation. Different total orders may lead to the same acyclic orientation, so an -vertex graph can have fewer than  acyclic orientations. The number of acyclic orientations is equal to χ(−1)}}, where  is the chromatic polynomial of the given graph.

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)} ，其中是给定图的色多项式。

任何无向图都可以通过为其顶点选择一个总的顺序，并按顺序将前一个端点的每条边定向到后一个端点，从而构成一个 DAG。所得到的边的方向称为无圈方向。不同的总序可能导致相同的无圈取向，因此一个顶点图可以有少于个无圈取向。非循环取向的个数等于 χ (- 1)} ，其中是给定图的色多项式。

| year = 1987

[[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.]]

 

condensation of the blue directed graph. It is formed by contracting each strongly connected component of the blue graph into a single yellow vertex.]]

 

 

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.

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.

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

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''^''ω'')}} where {{math|''ω''&nbsp;<&nbsp;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>

 

| 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.

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

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>

 

| 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.

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条路径连接的顶点对。传递约简由形成长度的边组成——一条路径是连接其端点的唯一路径。因此，传递约简可以在与传递闭包相同的渐近时间范围内构造。

在所有这些传递闭包算法中，可以区分至少一条长度为2条或更多的路径可到达的顶点对和只能通过一条长度为1条路径连接的顶点对。传递约简由形成长度的边组成——一条路径是连接其端点的唯一路径。因此，传递约简可以在与传递闭包相同的渐近时间范围内构造。

  | year = 1994| isbn = 978-0897916509 | s2cid = 18710118 }}.</ref>

  | journal = [[Management Science (journal)|Management Science]] | mr = 0403596 | pages = 1268–1272 | title = Maximal closure of a graph and applications to combinatorial problems | volume = 22

| year = 1976}}.</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.

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.

== Computational problems ==

== Computational problems ==