| 第32行： |
第32行： |
| | 有向无环图的拓扑排序族等同于其可达性的<font color="#ff8000"> 线性拓展Linear extension</font>族。 [10]因此，偏序关系相同的任意两个图会有相同的拓扑排序集。 | | 有向无环图的拓扑排序族等同于其可达性的<font color="#ff8000"> 线性拓展Linear extension</font>族。 [10]因此，偏序关系相同的任意两个图会有相同的拓扑排序集。 |
| | | | |
| − | === 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 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>
| |
| − | | |
| − | | |
| − | 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
| |
| − | :1, 1, 3, 25, 543, 29281, 3781503, … {{OEIS|id=A003024}}.
| |
| − | | |
| − | <font color="#ff8000"> 罗宾逊 Robinson</font>(1973)研究了有向无环图的<font color="#ff8000"> 图计数Graph enumeration</font>问题。如标号顶点在拓扑排序中出现的顺序不受限制，有n个顶点的标号有向无环图的数量为
| |
| − | 1, 1, 3, 25, 543, 29281, 3781503, … （OEIS中的数列A003024）。
| |
| − | 其中n = 0, 1, 2, 3,……。
| |
| − | | |
| − | These numbers may be computed by the recurrence relation
| |
| − | 这个数列的<font color="#ff8000"> 递推关系式 Recurrence relation</font>是
| |
| − | | |
| − | <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>
| |
| − | | |
| − | 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>
| |
| − | | |
| | <font color="#ff8000"> 埃里克·韦斯坦因 Eric W. Weisstein</font>推测[13]，n个顶点的标号有向无环图的数量与其中所有特征值都为正实数的n*n逻辑矩阵的数量相同。这一点随后被<font color="#ff8000"> McKay</font> et al. (2004) 证实，证明采用了<font color="#ff8000"> 双射法Bijective</font>：一个矩阵A是有向无环图的一个<font color="#ff8000"> 邻接矩阵Adjacency matrix</font>，当且仅当A + I 是一个所有特征值都为正数的逻辑矩阵，其中I 为<font color="#ff8000"> 单位矩阵 Identity matrix</font>。因为一个有向无环图不允许<font color="#ff8000"> 自环Self-loops</font>，它的邻接矩阵的对角线必定全为0。因此，加上I 保持了所有矩阵因子都是0或1的特性。[13] | | <font color="#ff8000"> 埃里克·韦斯坦因 Eric W. Weisstein</font>推测[13]，n个顶点的标号有向无环图的数量与其中所有特征值都为正实数的n*n逻辑矩阵的数量相同。这一点随后被<font color="#ff8000"> McKay</font> et al. (2004) 证实，证明采用了<font color="#ff8000"> 双射法Bijective</font>：一个矩阵A是有向无环图的一个<font color="#ff8000"> 邻接矩阵Adjacency matrix</font>，当且仅当A + I 是一个所有特征值都为正数的逻辑矩阵，其中I 为<font color="#ff8000"> 单位矩阵 Identity matrix</font>。因为一个有向无环图不允许<font color="#ff8000"> 自环Self-loops</font>，它的邻接矩阵的对角线必定全为0。因此，加上I 保持了所有矩阵因子都是0或1的特性。[13] |
| | | | |