7,129
个编辑
更改
跳到导航
跳到搜索
第34行：
第34行： + + 第45行：
第47行： + 第71行：
第74行： − +
→数学性质
[[file:A_topological_ordering_of_a_directed_acyclic_graph.png|thumb|right|175px|图5：一个有向无环图的拓扑排序：每一条边都从排序的前一条（左上）到排序的后一条（右下）。有向图是无环的当且仅当它具有拓扑序]] [[file:Transitive_Closure.svg.png|thumb|right|124px|图6：将红色边添加到蓝色有向无环图中会产生另一个DAG，即蓝色图的传递闭包。对于每个红边或蓝边uv，v可以从u到达：存在一条从u开始到v结束的蓝色路径。]]
[[file:A_topological_ordering_of_a_directed_acyclic_graph.png|thumb|right|175px|图5：一个有向无环图的拓扑排序：每一条边都从排序的前一条（左上）到排序的后一条（右下）。有向图是无环的当且仅当它具有拓扑序]] [[file:Transitive_Closure.svg.png|thumb|right|124px|图6：将红色边添加到蓝色有向无环图中会产生另一个DAG，即蓝色图的传递闭包。对于每个红边或蓝边uv，v可以从u到达：存在一条从u开始到v结束的蓝色路径。]]
有向无环图的<font color="#ff8000"> '''拓扑排序 Topological ordering''' </font>为所有边的起点都出现在其终点之前的排序。能构成拓扑排序的图一定没有环，因为环中的一条边必定从排序较后的顶点指向比其排序更前的顶点。<ref name="bang" />基于此，拓扑排序可以被用来定义有向无环图：当且仅当一个有向图有拓扑排序，它是有向无环图。一般情况下，拓扑排序并非唯一。有向无环图仅仅在存在一条路径可以包含其所有顶点的情况下，有唯一的拓扑排序方式，这时，拓扑排序与它们在这条路径中出现的顺序相同。<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>
有向无环图的<font color="#ff8000"> '''拓扑排序 Topological ordering''' </font>为所有边的起点都出现在其终点之前的排序。能构成拓扑排序的图一定没有环，因为环中的一条边必定从排序较后的顶点指向比其排序更前的顶点。<ref name="bang" />基于此，拓扑排序可以被用来定义有向无环图：当且仅当一个有向图有拓扑排序，它是有向无环图。一般情况下，拓扑排序并非唯一。有向无环图仅仅在存在一条路径可以包含其所有顶点的情况下，有唯一的拓扑排序方式，这时，拓扑排序与它们在这条路径中出现的顺序相同。<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>
有向无环图的拓扑排序族等同于其可达性的<font color="#ff8000"> '''线性拓展 Linear extension''' </font>族。 <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>因此，偏序关系相同的任意两个图会有相同的拓扑排序集。
有向无环图的拓扑排序族等同于其可达性的<font color="#ff8000"> '''线性拓展 Linear extension''' </font>族。 <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>因此，偏序关系相同的任意两个图会有相同的拓扑排序集。
===组合计数===
===组合计数===
:<math>a_n = \sum_{k=1}^n (-1)^{k-1} {n\choose k}2^{k(n-k)} a_{n-k}.</math><ref name="enum" />
:<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 <ref>{{MathWorld | urlname=WeissteinsConjecture | title=Weisstein's Conjecture}}</ref>，{{mvar|n}}个顶点的标号有向无环图的数量与其中所有<font color="#ff8000"> '''特征值 Eigenvalues''' </font>都为正实数的{{math|n*n}}<font color="#ff8000"> '''逻辑矩阵''' </font>的数量相同。这一点随后被 McKay 证实，证明采用了<font color="#ff8000"> '''双射法 Bijective'''</font>：一个矩阵{{mvar|A}}是有向无环图的一个<font color="#ff8000"> '''邻接矩阵 Adjacency matrix''' </font>，当且仅当{{math|''A'' + ''I''}}是一个所有特征值都为正数的逻辑矩阵，其中{{mvar|I}}为<font color="#ff8000"> '''单位矩阵 Identity matrix''' </font>。因为一个有向无环图不允许<font color="#ff8000"> '''自环 Self-loops''' </font>，它的邻接矩阵的对角线必定全为0。因此，加上{{mvar|I}}保持了所有矩阵因子都是0或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 <ref>{{MathWorld | urlname=WeissteinsConjecture | title=Weisstein's Conjecture}}</ref>，{{mvar|n}}个顶点的标号有向无环图的数量与其中所有<font color="#ff8000"> '''特征值 Eigenvalues''' </font>都为正实数的{{math|n*n}}<font color="#ff8000"> '''逻辑矩阵''' </font>的数量相同。这一点随后被 McKay 证实，证明采用了<font color="#ff8000"> '''双射法 Bijective'''</font>：一个矩阵{{mvar|A}}是有向无环图的一个<font color="#ff8000"> '''邻接矩阵 Adjacency matrix''' </font>，当且仅当{{math|''A'' + ''I''}}是一个所有特征值都为正数的逻辑矩阵，其中{{mvar|I}}为<font color="#ff8000"> '''单位矩阵 Identity matrix''' </font>。因为一个有向无环图不允许<font color="#ff8000"> '''自环 Self-loops''' </font>，它的邻接矩阵的对角线必定全为0。因此，加上{{mvar|I}}保持了所有矩阵因子都是0或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>
===相关概念===
===相关概念===
| title = Proc. SIGCHI conference on Human Factors in Computing Systems (CHI '94)
| title = Proc. SIGCHI conference on Human Factors in Computing Systems (CHI '94)
| year = 1994| isbn = 978-0897916509 }}.</ref>
| year = 1994| isbn = 978-0897916509 }}.</ref>
<br>
==相关计算问题==
==相关计算问题==