更改

有向无环图的拓扑排序族等同于其可达性的<font color="#ff8000"> 线性拓展Linear extension</font>族。 [10]因此，偏序关系相同的任意两个图会有相同的拓扑排序集。

有向无环图的拓扑排序族等同于其可达性的<font color="#ff8000"> 线性拓展Linear extension</font>族。 [10]因此，偏序关系相同的任意两个图会有相同的拓扑排序集。

=== Combinatorial enumeration ===

=== Combinatorial enumeration 组合计数===

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

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

The number of DAGs on {{mvar|n}} labeled vertices, for {{math|1=''n''&nbsp;=&nbsp;0, 1, 2, 3, …}} (without restrictions on the order in which these numbers appear in a topological ordering of the DAG) is

The number of DAGs on {{mvar|n}} labeled vertices, for {{math|1=''n''&nbsp;=&nbsp;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

These numbers may be computed by the recurrence relation

 

这个数列的<font color="#ff8000"> 递推关系式 Recurrence relation</font>是

 

: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}.</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>证明了同一个数可以计算所有特征值为正实数的(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>

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