更改

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

2021年6月14日 (一) 11:54的版本

删除859字节、 2021年6月14日 (一) 11:54

无编辑摘要

第6行：第6行：

==定义==

图是由顶点和连接顶点对的边组成的，顶点可以是任何一种由边成对连接的对象。在有向图中，每条边都有一个方向，从一个顶点到另一个顶点。

−

有向图中的 '''路径 Path''' 是不重复的顶点<math>i_1,…,i_m</math>（至少2个）的序列，满足对于所有的<math>k=1,…,{m−1}</math>存在边在顶点<math>i_k</math>和顶点<math>i_{k+1}</math>之间; 如果一条路的第一条边的起始顶点与它的最后一条边的结束顶点相同，那么它就形成了一个环。有向无环图即为没有环出现的有向图。<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''' 是不重复的顶点<math>i_1,…,i_m</math>（至少2个）的序列，满足对于所有的<math>k=1,…,{m−1}</math>存在边在顶点<math>i_k</math>和顶点<math>i_{k+1}</math>之间; 如果一条路的第一条边的起始顶点与它的最后一条边的结束顶点相同，那么它就形成了一个环。有向无环图即为没有环出现的有向图。<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||publisher=Academic Press|year=1975|pages=170–174}}.</ref>

第17行：第17行：

[[file:Transitive_reduction_of_G.png|thumb|right|124px|图3：有向无环图G的传递规约]]

−

有向无环图的 '''可达性 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|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''}}。

第33行：第33行：

===拓扑排序===

−

有向无环图的 '''拓扑排序 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|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>

第40行：第40行：

===组合计数===

−

罗宾逊 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|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 |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>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.|last2=Royle|first2=G. F.last3=Wanless|first3=I. M.|last4=Oggier|first4=F. E. |last5=Sloane|first5=N. J. A.|last6=Wilf|first6=H.|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>

第56行：第56行：

| last2 = Pearl

| first2 = Judea

−

~~| author2-link = Judea Pearl~~

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

| pages = 222–228

第62行：第61行：

| 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> 多重树必定是有向无环图。对于有根树，将其所有边赋予指离根的方向也可以得到有向无环图，即 '''树状图''' 。

+

}}.</ref> 多重树必定是有向无环图。对于有根树，将其所有边赋予指离根的方向也可以得到有向无环图，即 '''树状图''' 。

强明确树 Multitree 是每两个顶点最多被一条路径所连接的有向无环图。等价的说，它是满足以下性质的一个有向无环图：对于图中每个顶点{{mvar|v}}，从{{mvar|v}}可达的顶点组成一颗树。<ref>{{citation

−

| last1 = Furnas | first1 = George W. ~~| author1-link = George Furnas~~

+

| last1 = Furnas | first1 = George W.

| last2 = Zacks | first2 = Jeff

| contribution = Multitrees: enriching and reusing hierarchical structure

第91行：第90行：

===拓扑排序和识别===

−

可以用 '''线性时间复杂度''' 的卡恩算法来找到一个有向无环图的拓扑排序。<ref name="clrs">~~{{Introduction to Algorithms|edition=2}}~~ Section 22.4, Topological sort, pp. 549–552.</ref>简单来说，开设一个存放结果的列表{{mvar|L}}，先将入度为零的节点放到{{mvar|L}}中，因为这些节点没有任何的父节点。将与这些节点相连的边从图中去掉，再寻找图中入度为零的节点。对于新找到的节点来说，他们的父节点已经都在{{mvar|L}}中了，所以也可以从末端插入{{mvar|L}}。重复上述操作，直到找不到入度为零的节点。<ref name="j50" /> 另外一种构造拓扑排序的算法是将 '''深度优先搜索''' 的 '''后序遍历''' 结果翻转。<ref name="clrs" />

+

可以用 '''线性时间复杂度''' 的卡恩算法来找到一个有向无环图的拓扑排序。<ref name="clrs">Section 22.4, Topological sort, pp. 549–552.</ref>简单来说，开设一个存放结果的列表{{mvar|L}}，先将入度为零的节点放到{{mvar|L}}中，因为这些节点没有任何的父节点。将与这些节点相连的边从图中去掉，再寻找图中入度为零的节点。对于新找到的节点来说，他们的父节点已经都在{{mvar|L}}中了，所以也可以从末端插入{{mvar|L}}。重复上述操作，直到找不到入度为零的节点。<ref name="j50" /> 另外一种构造拓扑排序的算法是将 '''深度优先搜索''' 的 '''后序遍历''' 结果翻转。<ref name="clrs" />

第99行：第98行：

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

−

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

+

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

[[file:The_yellow_directed_acyclic_graph.png|thumb|right|175px|图9：黄色有向无环图是蓝色有向图的缩合。它是通过将蓝色图的每个强连通部分收缩为一个黄色顶点而形成的]]

−

任意有环有向图都可以被转化为有向无环图。只要从图中移除 '''反馈节点集 Feedback vertex set''' 或 '''反馈边集 Feedback arc set''' ，即对于图中每个环，至少包括环中一个顶点或边的集合。不过，找到反馈节点或边的最小集合是 '''NP困难 NP-hard''' 问题。<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困难 NP-hard''' 问题。<ref>{{citation | last1=Garey | first1=Michael R. | last2=Johnson | first2=David S. | year=1979| title=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|last2=Norman|first2=Robert Z.|last3=Cartwright|first3=Dorwin|publisher=John Wiley & Sons|year=1965|page=63}}.</ref> 对于无环图，它的最小反馈顶点或边集为 '''空集''' ，它的强连通分量则为自身。

第136行：第135行：

有向无环图的偏序关系可以在调度上有着先后顺序限制的系统任务中发挥作用。<ref>Skiena, Steven S. (2009), The Algorithm Design Manual, Springer, pp. 179–181, ISBN 978-1-84800-070-4..</ref>调度问题的一个重要种类是串联需要更新的对象，如[[电子计算表]]中某个单元格的计算公式依赖于其他单元格，或在程序的[[源代码]]被修改后重新编译[[目标代码|目标文件]]。 '''依赖图 Dependency graph''' 则记录了这种更新依赖关系。其每个顶点对应一个需要被更新的对象，边则表示更新的关系。依赖图中的环被称为 '''环状依赖 Circular dependency''' 。环状依赖通常是不被允许出现的，因为不能保证圈内任务排定顺序的一致性。无环的依赖图即为有向无环图。<ref>{{citation | last1=Al-Mutawa | first1=H. A. | last2=Dietrich | first2=J. | last3=Marsland | first3=S. | last4=McCartin | first4=C. | contribution=On the shape of circular dependencies in Java programs | doi=10.1109/ASWEC.2014.15 | pages=48–57 | publisher=IEEE | title=23rd Australian Software Engineering Conference | year=2014| isbn=978-1-4799-3149-1 }}.</ref>

−

举例来说，当电子表格中一个单元格的数值发生改变，其他直接或间接依赖于该单元格的所有单元格的值都需要被重新计算。被调度的任务为重新计算某个特定单元格的值。当一个单元格的值取决于另外一个单元格时，两个单元格之间则有依赖关系。每个被依赖单元格的值的计算过程都必须先于使用它的表达式执行。使用依赖图的拓扑排序来调度任务使得在每个单元格的值都仅被重新计算一次的情况下，整个工作表都能被更新。<ref name="hgt1181">{{citation |title=Handbook of Graph Theory |first1=Jonathan L. |last1=Gross |first2=Jay |last2=Yellen |first3=Ping |last3=Zhang ~~| author3-link = Ping Zhang (graph theorist)~~|edition=2nd |publisher=CRC Press |year=2013 |isbn=978-1-4398-8018-0 |page=1181 |url=https://books.google.com/books?id=cntcAgAAQBAJ&pg=PA1181}}.</ref>相似的任务调度场景出现在程序源代码编译的 '''Makefile''' ，<ref name="hgt1181" />和优化计算机程序底层执行的[[指令调度]]中。<ref>{{citation |title=The Compiler Design Handbook: Optimizations and Machine Code Generation |first1=Y. N. |last1=Srikant |first2=Priti |last2=Shankar |edition=2nd |publisher=CRC Press|year=2007 |isbn=978-1-4200-4383-9 |pages=19–39 |url=https://books.google.com/books?id=1kqAv-uDEPEC&pg=SA19-PA39}}.</ref>

+

举例来说，当电子表格中一个单元格的数值发生改变，其他直接或间接依赖于该单元格的所有单元格的值都需要被重新计算。被调度的任务为重新计算某个特定单元格的值。当一个单元格的值取决于另外一个单元格时，两个单元格之间则有依赖关系。每个被依赖单元格的值的计算过程都必须先于使用它的表达式执行。使用依赖图的拓扑排序来调度任务使得在每个单元格的值都仅被重新计算一次的情况下，整个工作表都能被更新。<ref name="hgt1181">{{citation |title=Handbook of Graph Theory |first1=Jonathan L. |last1=Gross |first2=Jay |last2=Yellen |first3=Ping |last3=Zhang |edition=2nd |publisher=CRC Press |year=2013 |isbn=978-1-4398-8018-0 |page=1181 |url=https://books.google.com/books?id=cntcAgAAQBAJ&pg=PA1181}}.</ref>相似的任务调度场景出现在程序源代码编译的 '''Makefile''' ，<ref name="hgt1181" />和优化计算机程序底层执行的[[指令调度]]中。<ref>{{citation |title=The Compiler Design Handbook: Optimizations and Machine Code Generation |first1=Y. N. |last1=Srikant |first2=Priti |last2=Shankar |edition=2nd |publisher=CRC Press|year=2007 |isbn=978-1-4200-4383-9 |pages=19–39 |url=https://books.google.com/books?id=1kqAv-uDEPEC&pg=SA19-PA39}}.</ref>

第161行：第160行： −

举例来说，'''贝叶斯网络 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. |last2=Dawid|first2=A. Philip|last3=Lauritzen|first3=Steffen L.|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|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>

第197行：第196行： −

在[[计算几何]]领域，许多随机化算法都会维护一个“历史有向无环图”，用以记录结构变动中的旧几何结构。例如，在 '''德劳内三角化 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|first2=Micha|last2=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>

第209行：第208行：

===数据压缩===

[[Image:分别用trie（左）和有向无环词图（右）存放英文单词.png|thumb|right|250px|图12：分别用trie（左）和有向无环词图（右）存放英文单词“tap”，“taps”，“top”和“tops”。<tt>EOW</tt>表示单词结束。]]

−

有向无环图也可以用于对一系列序列的[[数据压缩|压缩]]中。在这里，有向无环图中的路径代表这些序列。当多个序列有共同的子序列时，子序列可以被表示为这些序列对应路径的公共边。比起直接列出所有序列，这种方法占用更少空间。例如， '''无环确定有限状态自动机 Deterministic acyclic finite state automaton''' 为仅含单个源（入度为0的顶点）的有向无环图，其每条边附有一个或多个字符。每条其源到汇（出度为0的节点）的路径均代表一个[[字符串]]，字符串可以是英文单词。<ref>{{citation | first1=Maxime | last1=Crochemore | first2=Renaud | last2=Vérin | contribution=Direct construction of compact directed acyclic word graphs | series=Lecture Notes in Computer Science | publisher=Springer | title=Combinatorial Pattern Matching | volume=1264 | year=1997 | pages=116–129 | doi=10.1007/3-540-63220-4_55 | isbn=978-3-540-63220-7 | citeseerx=10.1.1.53.6273 }}.</ref>与其结构不同但功能相似的树称为[[trie]]。相比于trie，有向无环词图允许多条边指向同一个顶点，使得具有相同后缀的一些词的词头可以被相同的顶点所表示，因而更省空间。<ref>{{citation|title=Applied Combinatorics on Words|volume=105|series=Encyclopedia of Mathematics and its Applications|first=M.|last=~~Lothaire|authorlink=M.~~ Lothaire|publisher=Cambridge University Press|year=2005|isbn=9780521848022|page=18|url=https://books.google.com/books?id=fpLUNkj1T1EC&pg=PA18}}.</ref>

+

有向无环图也可以用于对一系列序列的[[数据压缩|压缩]]中。在这里，有向无环图中的路径代表这些序列。当多个序列有共同的子序列时，子序列可以被表示为这些序列对应路径的公共边。比起直接列出所有序列，这种方法占用更少空间。例如， '''无环确定有限状态自动机 Deterministic acyclic finite state automaton''' 为仅含单个源（入度为0的顶点）的有向无环图，其每条边附有一个或多个字符。每条其源到汇（出度为0的节点）的路径均代表一个[[字符串]]，字符串可以是英文单词。<ref>{{citation | first1=Maxime | last1=Crochemore | first2=Renaud | last2=Vérin | contribution=Direct construction of compact directed acyclic word graphs | series=Lecture Notes in Computer Science | publisher=Springer | title=Combinatorial Pattern Matching | volume=1264 | year=1997 | pages=116–129 | doi=10.1007/3-540-63220-4_55 | isbn=978-3-540-63220-7 | citeseerx=10.1.1.53.6273 }}.</ref>与其结构不同但功能相似的树称为[[trie]]。相比于trie，有向无环词图允许多条边指向同一个顶点，使得具有相同后缀的一些词的词头可以被相同的顶点所表示，因而更省空间。<ref>{{citation|title=Applied Combinatorics on Words|volume=105|series=Encyclopedia of Mathematics and its Applications|first=M.|last=Lothaire|publisher=Cambridge University Press|year=2005|isbn=9780521848022|page=18|url=https://books.google.com/books?id=fpLUNkj1T1EC&pg=PA18}}.</ref>

薄荷

7,129

个编辑

更改

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

2021年6月14日 (一) 11:54的版本

导航菜单

搜索