更改

有向无环图 (查看源代码)

2021年6月3日 (四) 22:49的版本

添加248字节、 2021年6月3日 (四) 22:49

无编辑摘要

第1行：第1行： −

在图论和计算机科学中，有向无环图 Directed acyclic graph（DAG 或 dag）是一个没有定向循环的有向图。也就是说，它由 顶点 Vertex 和 边 Edge (也称为弧)组成，每条边都从一个顶点指向另一个顶点，沿着这些顶点的方向不会形成一个闭合的 环 Loop 。有向图是一个有向无环图当且仅当它可以通过将顶点按照与所有边方向一致的线性顺序排列构成 拓扑排序 Topologically ordered 。有向无环图有许多科学的和计算的应用，从生物学(进化论，家谱，流行病学)到社会学(引文网络)到计算(调度)。

+

在图论和计算机科学中，'''有向无环图 Directed acyclic graph'''（DAG 或 dag）是一个没有定向循环的有向图。也就是说，它由 '''顶点 Vertex''' 和 '''边 Edge''' (也称为弧)组成，每条边都从一个顶点指向另一个顶点，沿着这些顶点的方向不会形成一个闭合的 '''环 Loop''' 。有向图是一个有向无环图当且仅当它可以通过将顶点按照与所有边方向一致的线性顺序排列构成 '''拓扑排序 Topologically ordered''' 。有向无环图有许多科学的和计算的应用，从生物学(进化论，家谱，流行病学)到社会学(引文网络)到计算(调度)。

==定义==

−

图是由顶点和连接顶点对的边组成的，顶点可以是任何一种由边成对连接的对象。在有向图中，每条边都有一个方向，从一个顶点到另一个顶点。有向图中的 路径 Path 是一个边序列，序列中每条边的结束顶点是序列中下一条边的起始顶点; 如果一条路的第一条边的起始顶点与它的最后一条边的结束顶点相同，那么它就形成了一个环。有向无环图即为没有环出现的有向图。<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>

+

图是由顶点和连接顶点对的边组成的，顶点可以是任何一种由边成对连接的对象。在有向图中，每条边都有一个方向，从一个顶点到另一个顶点。有向图中的 '''路径 Path''' 是一个边序列，序列中每条边的结束顶点是序列中下一条边的起始顶点; 如果一条路的第一条边的起始顶点与它的最后一条边的结束顶点相同，那么它就形成了一个环。有向无环图即为没有环出现的有向图。<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>

−

当存在一条从顶点u到顶点v的路径时，顶点v被称作是从顶点u 可达的 Reachability 。每个顶点都是从自身可达的（通过一条没有边的路径）。如果一个顶点可以从一条 非平凡路径（一条由一个或更多边组成的路径）到达自身，那么这条路径就是一个环。因此，有向无环图也可以被定义为没有顶点可以通过非平凡路径到达自身的图。<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>

+

当存在一条从顶点u到顶点v的路径时，顶点v被称作是从顶点u '''可达的 Reachability''' 。每个顶点都是从自身可达的（通过一条没有边的路径）。如果一个顶点可以从一条 非平凡路径（一条由一个或更多边组成的路径）到达自身，那么这条路径就是一个环。因此，有向无环图也可以被定义为没有顶点可以通过非平凡路径到达自身的图。<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>

== 数学性质 ==

第11行：第11行：

=== 可达性，传递闭包和传递归约 ===

−

有向无环图的 可达性 Reachability 可以用其顶点的 偏序关系 Partial order{{math|≤}}来表示。在偏序关系中，如果存在一条路径从顶点{{mvar|u}}指向顶点{{mvar|v}}，它们的偏序关系可被写作{{math|''u'' ≤ ''v''}}。这也被称作{{mvar|v}}是从{{mvar|u}}可达的。<ref>{{citation|title=The Design and Analysis of Algorithms|series=Monographs in Computer Science|first=Dexter|last=Kozen|authorlink=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>不同的有向无环图可以有着相同的可达关系和偏序关系。<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>例如，有两条边{{math|''a'' → ''b''}}，{{math|''b'' → ''c''}}的有向无环图，和有三条边的{{math|''a'' → ''b''}}, {{math|''b'' → ''c''}}，{{math|''a'' → ''c''}}的有向无环图有着相同的偏序关系{{math|''a'' ≤ ''b'' ≤ ''c''}}。

+

有向无环图的 '''可达性 Reachability''' 可以用其顶点的 '''偏序关系 Partial order''' {{math|≤}}来表示。在偏序关系中，如果存在一条路径从顶点{{mvar|u}}指向顶点{{mvar|v}}，它们的偏序关系可被写作{{math|''u'' ≤ ''v''}}。这也被称作{{mvar|v}}是从{{mvar|u}}可达的。<ref>{{citation|title=The Design and Analysis of Algorithms|series=Monographs in Computer Science|first=Dexter|last=Kozen|authorlink=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>不同的有向无环图可以有着相同的可达关系和偏序关系。<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>例如，有两条边{{math|''a'' → ''b''}}，{{math|''b'' → ''c''}}的有向无环图，和有三条边的{{math|''a'' → ''b''}}, {{math|''b'' → ''c''}}，{{math|''a'' → ''c''}}的有向无环图有着相同的偏序关系{{math|''a'' ≤ ''b'' ≤ ''c''}}。

−

对于一个有向无环图{{mvar|G}}，它的 传递闭包 Transitive closure 等同于一个在保持与其相同可达性的情况下，边数最多的图。在这个图中，当{{mvar|u}}可达{{mvar|v}}的时候，边{{math|''u'' → ''v''}}必定存在。换句话说，每个{{mvar|G}}中的非相同元素偏序关系对{{math|''u'' ≤ ''v''}}都在这个图中有一条边。这可以被视作用图来可视化图{{mvar|G}}的可达性关系。

+

对于一个有向无环图{{mvar|G}}，它的 '''传递闭包 Transitive closure''' 等同于一个在保持与其相同可达性的情况下，边数最多的图。在这个图中，当{{mvar|u}}可达{{mvar|v}}的时候，边{{math|''u'' → ''v''}}必定存在。换句话说，每个{{mvar|G}}中的非相同元素偏序关系对{{math|''u'' ≤ ''v''}}都在这个图中有一条边。这可以被视作用图来可视化图{{mvar|G}}的可达性关系。

−

有向无环图{{mvar|G}}的 传递规约 Transitive reduction 为和其有着相同可达性，边数最少的图。它是{{mvar|G}}的一个子图。构造方法为当{{mvar|G}}有着一条更长的路径连接顶点{{mvar|u}}和{{mvar|v}}的时候，消去边{{math|''u'' → ''v''}}。

+

有向无环图{{mvar|G}}的 '''传递规约 Transitive reduction''' 为和其有着相同可达性，边数最少的图。它是{{mvar|G}}的一个子图。构造方法为当{{mvar|G}}有着一条更长的路径连接顶点{{mvar|u}}和{{mvar|v}}的时候，消去边{{math|''u'' → ''v''}}。

传递约简和传递闭包都是有向无环图的特有概念。相反的，对于有向有环图，可以存在多个与原图有着相同可达性的最简子图。<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>

−

对于有向无环图G和表达其可达性的偏序关系≤，它的传递规约也可以看作包含G的 覆盖关系 Covering relation 中每一条边的G的子图。传递规约在图示有向无环图的偏序关系时十分有用，因为它们比其他具有相同偏序关系的图的边数要少，这简化了绘图。偏序关系的 哈斯图 Hasse diagram 由将传递规约中的每条边的起点绘制在其终点的下方而得到。<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>

+

对于有向无环图G和表达其可达性的偏序关系≤，它的传递规约也可以看作包含G的 '''覆盖关系 Covering relation''' 中每一条边的G的子图。传递规约在图示有向无环图的偏序关系时十分有用，因为它们比其他具有相同偏序关系的图的边数要少，这简化了绘图。偏序关系的 '''哈斯图 Hasse diagram''' 由将传递规约中的每条边的起点绘制在其终点的下方而得到。<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>

=== 拓扑排序===

−

有向无环图的 拓扑排序 Topological ordering 为所有边的起点都出现在其终点之前的排序。能构成拓扑排序的图一定没有环，因为环中的一条边必定从排序较后的顶点指向比其排序更前的顶点。<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>

+

有向无环图的 '''拓扑排序 Topological ordering''' 为所有边的起点都出现在其终点之前的排序。能构成拓扑排序的图一定没有环，因为环中的一条边必定从排序较后的顶点指向比其排序更前的顶点。<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>

−

有向无环图的拓扑排序族等同于其可达性的 线性拓展 Linear extension 族。 <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>因此，偏序关系相同的任意两个图会有相同的拓扑排序集。

+

有向无环图的拓扑排序族等同于其可达性的 '''线性拓展 Linear extension''' 族。 <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>因此，偏序关系相同的任意两个图会有相同的拓扑排序集。

=== 组合计数 ===

−

罗宾逊 Robinson (1973) 研究了有向无环图的 图计数 Graph enumeration 问题。<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

+

罗宾逊 Robinson (1973) 研究了有向无环图的 '''图计数 Graph enumeration''' 问题。<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>

如标号顶点在拓扑排序中出现的顺序不受限制，有{{mvar|n}}个顶点的标号有向无环图的数量为

:1, 1, 3, 25, 543, 29281, 3781503, … （OEIS中的数列A003024）。

−

其中{{math|1=''n'' = 0, 1, 2, 3,……}}。这个数列的 递推关系式 Recurrence relation 是

+

其中{{math|1=''n'' = 0, 1, 2, 3,……}}。这个数列的 '''递推关系式 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 <ref>{{MathWorld | urlname=WeissteinsConjecture | title=Weisstein's Conjecture}}</ref>，{{mvar|n}}个顶点的标号有向无环图的数量与其中所有 特征值 Eigenvalues 都为正实数的{{math|n*n}}逻辑矩阵的数量相同。这一点随后被 McKay 证实，证明采用了 双射法Bijective：一个矩阵{{mvar|A}}是有向无环图的一个 邻接矩阵 Adjacency matrix ，当且仅当{{math|''A'' + ''I''}}是一个所有特征值都为正数的逻辑矩阵，其中{{mvar|I}}为 单位矩阵 Identity matrix 。因为一个有向无环图不允许 自环 Self-loops ，它的邻接矩阵的对角线必定全为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}}个顶点的标号有向无环图的数量与其中所有 '''特征值 Eigenvalues''' 都为正实数的{{math|n*n}} '''逻辑矩阵''' 的数量相同。这一点随后被 McKay 证实，证明采用了 '''双射法Bijective'''：一个矩阵{{mvar|A}}是有向无环图的一个 '''邻接矩阵 Adjacency matrix''' ，当且仅当{{math|''A'' + ''I''}}是一个所有特征值都为正数的逻辑矩阵，其中{{mvar|I}}为 '''单位矩阵 Identity matrix''' 。因为一个有向无环图不允许 '''自环 Self-loops''' ，它的邻接矩阵的对角线必定全为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>

=== 相关概念 ===

−

多重树Polytree由将自由树的边定向Orienting而得到。<ref>{{citation

+

'''多重树Polytree''' 由将自由树的边 '''定向Orienting''' 而得到。<ref>{{citation

| last1 = Rebane

| first1 = George

第68行：第68行：

=== 从其他图构建===

−

任意无向图都可以被转化为有向无环图。构造方法是选定一个顶点的[[全序关系]]，并将无向图中所有边从全序关系中较前的顶点指向较后的顶点。这种方法是 定向 方法中的 无环定向 Acyclic orientation 。不同的全序关系可能推出相同的无环定向，因此一个包含{{mvar|n}}个顶点的图的无环定向数量小于{{math|''n''!}}。如果定义{{mvar|χ}}为给定图的[[色多项式]]，无环定向数量等于{{math|{{!}}''χ''(−1){{!}}}}。<ref>{{citation|first=Richard P.|last=Stanley|authorlink=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>

+

任意无向图都可以被转化为有向无环图。构造方法是选定一个顶点的[[全序关系]]，并将无向图中所有边从全序关系中较前的顶点指向较后的顶点。这种方法是 定向 方法中的 '''无环定向 Acyclic orientation''' 。不同的全序关系可能推出相同的无环定向，因此一个包含{{mvar|n}}个顶点的图的无环定向数量小于{{math|''n''!}}。如果定义{{mvar|χ}}为给定图的[[色多项式]]，无环定向数量等于{{math|{{!}}''χ''(−1){{!}}}}。<ref>{{citation|first=Richard P.|last=Stanley|authorlink=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>

−

任意有环有向图都可以被转化为有向无环图。只要从图中移除 反馈节点集 Feedback vertex set 或 反馈边集 Feedback arc set ，即对于图中每个环，至少包括环中一个顶点或边的集合。不过，找到反馈节点或边的最小集合是[[NP困难]]问题。<ref>{{citation | last1=Garey | first1=Michael R. | authorlink1=Michael Garey | last2=Johnson | first2=David S. | authorlink2=David S. Johnson | year=1979| title=[[Computers and Intractability|Computers and Intractability: A Guide to the Theory of NP-Completeness]]| publisher=[[W. H. Freeman and Company|W. H. Freeman]]| isbn=0-7167-1045-5| chapter = Problems GT7 and GT8| pages = 191–192}}</ref> 另外一种方法将有环有向图去环的方法是将每个强连通分量[[边收缩|收缩]]为一个顶点。<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> 对于无环图，它的最小反馈顶点或边集为[[空集]]，它的强连通分量则为自身。

+

任意有环有向图都可以被转化为有向无环图。只要从图中移除 '''反馈节点集 Feedback vertex set''' 或 '''反馈边集 Feedback arc set''' ，即对于图中每个环，至少包括环中一个顶点或边的集合。不过，找到反馈节点或边的最小集合是[[NP困难]]问题。<ref>{{citation | last1=Garey | first1=Michael R. | authorlink1=Michael Garey | last2=Johnson | first2=David S. | authorlink2=David S. Johnson | year=1979| title=[[Computers and Intractability|Computers and Intractability: A Guide to the Theory of NP-Completeness]]| publisher=[[W. H. Freeman and Company|W. H. Freeman]]| isbn=0-7167-1045-5| chapter = Problems GT7 and GT8| pages = 191–192}}</ref> 另外一种方法将有环有向图去环的方法是将每个强连通分量[[边收缩|收缩]]为一个顶点。<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> 对于无环图，它的最小反馈顶点或边集为[[空集]]，它的强连通分量则为自身。

=== 传递闭包和传递约简 ===

−

有向无环图的传递闭包可以通过 广度优先搜索 或 深度优先搜索 对每个节点测试可达性来构建。算法对于一个有着{{mvar|n}}个顶点和{{mvar|m}}条边的有向无环图的复杂度为{{math|''O''(''mn'')}}。<ref>{{harvtxt|Skiena|2009}}, p. 495.</ref>也可以使用 矩阵乘法算法 Matrix multiplication algorithm 中最快的 Coppersmith–Winograd算法，其复杂度为{{math|''O''(''n''''2.3728639'')}}。这个算法理论上在 稠密图 Dense graph中快过{{math|''O''(''mn'')}}。<ref>{{harvtxt|Skiena|2009}}, p. 496.</ref>

+

有向无环图的传递闭包可以通过 '''广度优先搜索''' 或 '''深度优先搜索''' 对每个节点测试可达性来构建。算法对于一个有着{{mvar|n}}个顶点和{{mvar|m}}条边的有向无环图的复杂度为{{math|''O''(''mn'')}}。<ref>{{harvtxt|Skiena|2009}}, p. 495.</ref>也可以使用 '''矩阵乘法算法 Matrix multiplication algorithm''' 中最快的 '''Coppersmith–Winograd算法'''，其复杂度为{{math|''O''(''n''''2.3728639'')}}。这个算法理论上在 '''稠密图 Dense graph'''中快过{{math|''O''(''mn'')}}。<ref>{{harvtxt|Skiena|2009}}, p. 496.</ref>

−

不论在哪种传递闭包算法中，那些被一条长度至少为2的路径所连接的顶点对，都可以和只有一条长度为1的路径所连接的顶点对区分开。由于传递约简包含后者，传递约简可以在和传递闭包相同的 渐进时间复杂度 Asymptotic computational complexity 中被构建。<ref>{{harvtxt|Bang-Jensen|Gutin|2008}}, p. 38.</ref>

+

不论在哪种传递闭包算法中，那些被一条长度至少为2的路径所连接的顶点对，都可以和只有一条长度为1的路径所连接的顶点对区分开。由于传递约简包含后者，传递约简可以在和传递闭包相同的 '''渐进时间复杂度 Asymptotic computational complexity''' 中被构建。<ref>{{harvtxt|Bang-Jensen|Gutin|2008}}, p. 38.</ref>

=== 闭包问题 ===

−

闭包是一个图中没有出边的顶点子集，即不存在从子集中顶点指向子集外顶点的边。 闭包问题 Closure problem 是则是找到带权图中使得权之和最大或最小的子集。闭包问题可以看作 最大流问题 的简化版，在 多项式时间 内被解决。实际上，是否有环对于找到闭包没有影响。<ref>{{citation

+

闭包是一个图中没有出边的顶点子集，即不存在从子集中顶点指向子集外顶点的边。 '''闭包问题 Closure problem''' 是则是找到带权图中使得权之和最大或最小的子集。闭包问题可以看作 '''最大流问题''' 的简化版，在 '''多项式时间''' 内被解决。实际上，是否有环对于找到闭包没有影响。<ref>{{citation

| last = Picard | first = Jean-Claude

| doi = 10.1287/mnsc.22.11.1268

第106行：第106行：

在电子电路设计中，静态[[组合逻辑电路]]块可以被表示为由[[逻辑门]]组成的有向无环系统。每个逻辑门对输入做一次函数处理，输入和输出均为一个[[位元]]组。通常，这些电路块的输出不能够再作为输入，除非它们被存储在寄存器或者状态单元中，以保证图不出现环。<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>

−

数据式编程 Dataflow programming 语言描述针对 数据流 Data stream 的操作，以及操作的输出和其他操作的输入之间的关系。这类型的语言使得描绘高重复率数据处理任务的变得更加简单，因为同样的数据操作可以应用于许多数据项。数据操作可以用有向无环图来表示。这些数据操作可以被[[平行演算法|并发]]执行，从而高效利用多核心[[中央处理器|处理器]]。<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>

+

'''数据式编程 Dataflow programming''' 语言描述针对 '''数据流 Data stream''' 的操作，以及操作的输出和其他操作的输入之间的关系。这类型的语言使得描绘高重复率数据处理任务的变得更加简单，因为同样的数据操作可以应用于许多数据项。数据操作可以用有向无环图来表示。这些数据操作可以被[[平行演算法|并发]]执行，从而高效利用多核心[[中央处理器|处理器]]。<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>

−

在[[编译器]]中，直线码（不含条件分支和循环的代码段）可以使用有向无环图表示。图标示出每个算术运算的输入和输出。这种表示法让编译器能执行 通用子表达式删除 Common subexpression elimination ，使得代码更高效。<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>

+

在[[编译器]]中，直线码（不含条件分支和循环的代码段）可以使用有向无环图表示。图标示出每个算术运算的输入和输出。这种表示法让编译器能执行 '''通用子表达式删除 Common subexpression elimination''' ，使得代码更高效。<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>

=== 因果结构 ===

第115行：第115行：

用顶点表示事件，边表示[[因果关系]]的图通常是无环的。<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=http://books.google.com/books?id=35MKXlKoXIUC&pg=PA4}}.</ref>事件由时间上的先后顺序来排列，所有箭头遵循从先发生事件指向后发生事件的原则，因此也不存在环。

−

举例来说，贝叶斯网络 Bayesian network 表示多个概率事件的关联网络。顶点表示事件，后续事件的发生可能性则可以通过其在有向无环图的前驱节点的发生概率计算出来。<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=http://books.google.com/books?id=RfshqEgO7KgC&pg=PA58}}.</ref>在此基础上，一个有向无环图的 端正图 Moral graph 通过以下方法而得到：将单个顶点的所有父节点之间添加一条无向边，再将所有的有向边换成无向边。<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= 0-387-98767-3 |chapter= 3.2.1 Moralization|pages= 31–33 }}.</ref>

+

举例来说，'''贝叶斯网络 Bayesian network''' 表示多个概率事件的关联网络。顶点表示事件，后续事件的发生可能性则可以通过其在有向无环图的前驱节点的发生概率计算出来。<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=http://books.google.com/books?id=RfshqEgO7KgC&pg=PA58}}.</ref>在此基础上，一个有向无环图的 '''端正图 Moral graph''' 通过以下方法而得到：将单个顶点的所有父节点之间添加一条无向边，再将所有的有向边换成无向边。<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= 0-387-98767-3 |chapter= 3.2.1 Moralization|pages= 31–33 }}.</ref>

−

另外一种具有相似因果结构的图是 影响图 Influence diagram 。其顶点表示决策或不确定的事件，边表示两个顶点之间的因果关系。<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-7|url=http://books.google.com/books?id=C2u8I0DFo4IC&pg=SA9-PA7}}.</ref>在流行病学中，这些表示因果关系的图表常常用来评估不同干预手段的效果。<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=http://books.google.com/books?id=wObgnN3x14kC&pg=PA255}}.</ref><ref name=pearl:95>{{cite journal|last1=Pearl|first1=Judea|authorlink= Judea Pearl|title=Causal diagrams for empirical research|journal=Biometrika|date=1995|volume=82|issue=4|pages=669–709|doi=10.1093/biomet/82.4.669}}</ref>

+

另外一种具有相似因果结构的图是 '''影响图 Influence diagram''' 。其顶点表示决策或不确定的事件，边表示两个顶点之间的因果关系。<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-7|url=http://books.google.com/books?id=C2u8I0DFo4IC&pg=SA9-PA7}}.</ref>在流行病学中，这些表示因果关系的图表常常用来评估不同干预手段的效果。<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=http://books.google.com/books?id=wObgnN3x14kC&pg=PA255}}.</ref><ref name=pearl:95>{{cite journal|last1=Pearl|first1=Judea|authorlink= Judea Pearl|title=Causal diagrams for empirical research|journal=Biometrika|date=1995|volume=82|issue=4|pages=669–709|doi=10.1093/biomet/82.4.669}}</ref>

=== 系谱学和版本历史 ===

[[File:EgyptianPtolemies2.jpg|thumb|upright=1.5|[[托勒密王朝]]的谱系图。]]

−

[[谱系图]]可以看作是有向无环图，顶点代表家族成员，边代表亲子关系。<ref>{{citation|journal=Algorithms for Molecular Biology|date=April 2011|volume=6|issue=10|pages=10|title=Haplotypes versus genotypes on pedigrees|first=Bonnie B.|last=Kirkpatrick|doi=10.1186/1748-7188-6-10|pmc=3102622|pmid=21504603}}.</ref>虽然谱系图也被称作为家族“树”, 但近亲结婚导致的~~~~ 血统崩溃 Pedigree collapse ~~~~会违反树的性质。即一个孩子的祖先既可以从父亲向上追溯，也可以从母亲一侧。<ref>{{citation

+

[[谱系图]]可以看作是有向无环图，顶点代表家族成员，边代表亲子关系。<ref>{{citation|journal=Algorithms for Molecular Biology|date=April 2011|volume=6|issue=10|pages=10|title=Haplotypes versus genotypes on pedigrees|first=Bonnie B.|last=Kirkpatrick|doi=10.1186/1748-7188-6-10|pmc=3102622|pmid=21504603}}.</ref>虽然谱系图也被称作为家族“树”, 但近亲结婚导致的血统崩溃 Pedigree collapse 会违反树的性质。即一个孩子的祖先既可以从父亲向上追溯，也可以从母亲一侧。<ref>{{citation

| last1 = McGuffin | first1 = M. J.

| last2 = Balakrishnan | first2 = R.

第147行：第147行：

基于相同的原因，一个[[分散式版本控制]]系统的版本历史的结构也是有向无环图。在系统中，每个版本对应一个节点。边连接起有直接衍生关系的两个版本。由于分支合并的存在，这个结构并不能用树来表示。<ref>{{citation|title=Architecture and Methods for Flexible Content Management in Peer-to-Peer Systems|first=Udo|last=Bartlang|publisher=Springer|year=2010|isbn=978-3-8348-9645-2|page=59|url=https://books.google.com/books?id=vXdEAAAAQBAJ&pg=PA59}}.</ref>

−

在[[计算几何]]领域，许多随机化算法都会维护一个“历史有向无环图”，用以记录结构变动中的旧几何结构。例如，在 德劳内三角化 Delaunay triangulation 的随机增量算法中，在添加每个点时，通过用三个较小的三角形替换一个三角形，以及通过“翻转”操作将三角形对替换为另一对三角形，来改变三角剖分。在该算法的历史有向无环图中，每个在算法中构建出的三角形对应一个顶点，边则将每个三角形和替代它的两个或三个三角形连接起来。这种图结构可以高效地处理 点定位 Point location 问题，即对于一个查询点{{mvar|q}}，找到它在德勞內三角剖分中的位置。在历史有向无环图中，从起点开始，不断移动到包含{{mvar|q}}的替代三角形组，最后到达的终点必定代表包含q的德劳内三角形。<ref>{{citation|title=Combinatorial Geometry and Its Algorithmic Applications: The Alcalá Lectures|volume=152|series=Mathematical surveys and monographs|first1=János|last1=Pach|author1-link=János Pach|first2=Micha|last2=Sharir|author2-link=Micha Sharir|publisher=American Mathematical Society|isbn=978-0-8218-7533-9|pages=93–94|url=https://books.google.com/books?id=-fguzNaYoqcC&pg=PA93}}.</ref>

+

在[[计算几何]]领域，许多随机化算法都会维护一个“历史有向无环图”，用以记录结构变动中的旧几何结构。例如，在 '''德劳内三角化 Delaunay triangulation''' 的随机增量算法中，在添加每个点时，通过用三个较小的三角形替换一个三角形，以及通过“翻转”操作将三角形对替换为另一对三角形，来改变三角剖分。在该算法的历史有向无环图中，每个在算法中构建出的三角形对应一个顶点，边则将每个三角形和替代它的两个或三个三角形连接起来。这种图结构可以高效地处理 '''点定位 Point location''' 问题，即对于一个查询点{{mvar|q}}，找到它在德勞內三角剖分中的位置。在历史有向无环图中，从起点开始，不断移动到包含{{mvar|q}}的替代三角形组，最后到达的终点必定代表包含q的德劳内三角形。<ref>{{citation|title=Combinatorial Geometry and Its Algorithmic Applications: The Alcalá Lectures|volume=152|series=Mathematical surveys and monographs|first1=János|last1=Pach|author1-link=János Pach|first2=Micha|last2=Sharir|author2-link=Micha Sharir|publisher=American Mathematical Society|isbn=978-0-8218-7533-9|pages=93–94|url=https://books.google.com/books?id=-fguzNaYoqcC&pg=PA93}}.</ref>

=== 引用图 ===

孙钦贵

387

个编辑

更改

有向无环图 (查看源代码)

2021年6月3日 (四) 22:49的版本

导航菜单

搜索