跳转到内容

有向无环图：修订间差异

维基百科，自由的百科全书
以互动方式浏览历史
←上一版本下一版本→
删除的内容 添加的内容
可视化wikitext
→系谱学和版本历史：​ 内容扩充
第146行： 第146行：
| year = 2001}}.</ref>
| year = 2001}}.</ref>


基于相同的原因， 一个[[分散式版本控制]]系统的版本历史的结构也是有向无环图。
基于相同的原因， 一个[[分散式版本控制]]系统的版本历史的结构也是有向无环图。在系统中，每个版本对应一个节点。边连接起有直接衍生关系的两个版本。由于分支合并的存在，这个结构并不能用树来表示。<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>

在[[计算几何]]领域，许多随机化算法都会维护一个“历史有向无环图”，用以记录结构变动中的旧几何结构。例如，在[[德勞內三角化]]的随机增量算法中，在添加每个点时，通过用三个较小的三角形替换一个三角形，以及通过“翻转”操作将三角形对替换为另一对三角形，来改变三角剖分。在该算法的历史有向无环图中，每个在算法中构建出的三角形对应一个顶点，边则将每个三角形和替代它的两个或三个三角形连接起来。


==参考文献==
==参考文献==

2020年5月31日 (日) 10:59的版本

一個有向無環圖的例子

在图论中，如果一个有向图从任意顶点出发无法经过若干条边回到该点，则这个图是一个有向无环图（DAG,directed acyclic graph）。[1]

因为有向图中一个点经过两种路线到达另一个点未必形成环，因此有向无环图未必能转化成树，但任何有向树均为有向无环图。

定义

图由顶点和连接这些顶点的边所构成。每条边都带有从一个顶点指向另一个顶点的方向的图为有向图。有向图中的道路为一系列的边，系列中每条边的终点都是下一条边的起点。如果一条路径的起点是这条路径的终点，那么这条路径就是一个环。有向无环图即为没有环出现的有向图。[2][3][4]

在以蓝线标识的有向无环图中，添加红线从而得到其传递闭包

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

数学性质

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

有向无环图的可达性可以用其顶点的偏序关系≤来表示。在偏序关系中，如果存在一条路径从顶点u指向顶点v，它们的偏序关系可被写作u ≤ v。这也被称作v是从u可达的。[6]不同的有向无环图可以有着相同的可达关系和偏序关系。[7]例如，有两条边a → b，b → c的有向无环图，和有三条边的a → b, b → c，a → c的有向无环图有着相同的偏序关系a ≤ b ≤ c。

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

有向无环图G
G的传递规约

有向无环图G的传递规约为和其有着相同可达性，边数最少的图。它是G的一个子图。构造方法为当G有着一条更长的路径连接顶点u和v的时候，消去边u → v。 传递约简和传递闭包都是有向无环图的特有概念。相反的，对于有向有环图，可以存在多个与原图有着相同可达性的最简子图。[8]

将{ x, y, z }的幂集按包含偏序排序得到的哈斯图

对于有向无环图G和表达其可达性的偏序关系≤，它的传递规约也可以看作包含G的覆盖关系（英语：covering relation）中每一条边的G的子图。传递规约在图示有向无环图的偏序关系时十分有用，因为它们比其他具有相同偏序关系的图的边数要少，这简化了绘图。偏序关系的哈斯图由将传递规约中的每条边的起点绘制在其终点的下方而得到。[9]

拓扑排序

有向无环图的拓扑排序为所有边的起点都出现在其终点之前的排序。能构成拓扑排序的图一定没有环，因为环中的一条边必定从排序较后的顶点指向比其排序更前的顶点。[3]基于此，拓扑排序可以被用来定义有向无环图：当且仅当一个有向图有拓扑排序，它是有向无环图。一般情况下，拓扑排序并非唯一。有向无环图仅仅在存在一条路径可以包含其所有顶点的情况下，有唯一的拓扑排序方式，这时，拓扑排序与它们在这条路径中出现的顺序相同。[10]

有向无环图的拓扑排序族等同于其可达性的线性拓展（英语：linear extension）族。 [11]因此，偏序关系相同的任意两个图会有相同的拓扑排序集。

组合计数

罗宾逊 (1973)研究了有向无环图的图计数（英语：graph enumeration）问题。[12] 如标号顶点在拓扑排序中出现的顺序不受限制，有n个顶点的标号有向无环图的数量为

1, 1, 3, 25, 543, 29281, 3781503, … （OEIS數列A003024）。

其中n = 0, 1, 2, 3,……。这个数列的递推关系式是

[12]

埃里克·韦斯坦因推测[13]，n个顶点的标号有向无环图的数量与其中所有特征值都为正实数的n*n逻辑矩阵的数量相同。这一点随后被证实，证明采用了双射法：一个矩阵A是有向无环图的一个邻接矩阵，当且仅当A + I是一个所有特征值都为正数的逻辑矩阵，其中I为单位矩阵。因为一个有向无环图不允许自环，它的邻接矩阵的对角线必定全为0。因此，加上I保持了所有矩阵因子都是0或1的特性。[14]

相关概念

一颗多重树
强明确树（英语：multitree）

多重树（英语：polytree）由将自由树的边定向（英语：orienting）而得到。[15] 多重树必定是有向无环图。对于有根树，将其所有边赋予指离根的方向也可以得到有向无环图，即树状图。

强明确树（英语：multitree）是每两个顶点最多被一条路径所连接的有向无环图。等价的说，它是满足以下性质的一个有向无环图：对于图中每个顶点v，从v可达的顶点组成一颗树。[16]

相关计算问题

拓扑排序和识别

主条目：拓扑排序

可以用线性时间复杂度的卡恩算法来找到一个有向无环图的拓扑排序。[17]简单来说，开设一个存放结果的列表L，先将入度为零的节点放到L中，因为这些节点没有任何的父节点。将与这些节点相连的边从图中去掉，再寻找图中入度为零的节点。对于新找到的节点来说，他们的父节点已经都在L中了，所以也可以从末端插入L。重复上述操作，直到找不到入度为零的节点。[18] 另外一种构造拓扑排序的算法是将深度优先搜索的后序遍历结果翻转。[17]

检查一个有向图是否为有向无环图亦可在线性时间内完成。一种方法是先找到一个拓扑排序，然后测试这个排序是否能符合图中每条边所连顶点在排序中应该出现的顺序。[19] 对于卡恩算法在内的部分拓扑排序算法，通过在算法终止时判断是否满足一定条件即可知道图是否有环。[18]如果有环，卡恩算法最终获得的L中节点个数会与图的节点总数不同。

从其他图构建

任意无向图都可以被转化为有向无环图。构造方法是选定一个顶点的全序关系，并将无向图中所有边从全序关系中较前的顶点指向较后的顶点。这种方法是定向（英语：Orientation (graph theory)）方法中的无环定向（英语：acyclic orientation）。不同的全序关系可能推出相同的无环定向，因此一个包含n个顶点的图的无环定向数量小于n!。如果定义χ为给定图的色多项式，无环定向数量等于|χ(−1)|。[20]

任意有环有向图都可以被转化为有向无环图。只要从图中移除反馈节点集（英语：feedback vertex set）或反馈边集（英语：feedback arc set），即对于图中每个环，至少包括环中一个顶点或边的集合。不过，找到反馈节点或边的最小集合是NP困难问题。[21] 另外一种方法将有环有向图去环的方法是将每个强连通分量收缩为一个顶点。[22] 对于无环图，它的最小反馈顶点或边集为空集，它的强连通分量则为自身。

传递闭包和传递约简

有向无环图的传递闭包可以通过广度优先搜索或深度优先搜索对每个节点测试可达性来构建。算法对于一个有着n个顶点和m条边的有向无环图的复杂度为O(mn)。[23]也可以使用矩阵乘法算法（英语：matrix multiplication algorithm）中最快的Coppersmith–Winograd算法（英语：Coppersmith–Winograd algorithm），其复杂度为O(n2.3728639)。这个算法理论上在稠密图（英语：dense graph）中快过O(mn)。[24]

不论在哪种传递闭包算法中，那些被一条长度至少为2的路径所连接的顶点对，都可以和只有一条长度为1的路径所连接的顶点对区分开。由于传递约简包含后者，传递约简可以在和传递闭包相同的渐进时间复杂度（英语：Asymptotic computational complexity）中被构建。[25]

闭包问题

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

最短或最长路径问题

基于拓扑排序的性质，有向无环图的最短路问题和最长路径问题可以在线性时间内解决。将顶点拓扑排序后，从前到后遍历每一个顶点，对于遍历到的顶点，更新其所有出边所到达顶点的长度值。如果求最短路，则在本边是更短路径的一部分时更新。求最长路则反之。[27]对于非有向无环图，最短路需要用复杂度为的戴克斯特拉算法或的贝尔曼-福特算法等。[28]最长路径则是一个NP困难问题。[29]

应用

调度

有向无环图的偏序关系可以在调度有着先后顺序限制的系统任务中发挥作用。[30]调度问题的一个重要种类是串联需要更新的对象，如電子試算表中某个单元格的计算公式依赖于其他单元格，或在程序的源代码被修改后重新编译目标文件。依赖图（英语：dependency graph）则记录了这种更新依赖关系。其每个顶点对应一个需要被更新的对象，边则表示更新的关系。依赖图中的环被称为环状依赖（英语：circular dependency）。环状依赖通常是不被允许出现的，因为不能保证圈内任务排定顺序的一致性。无环的依赖图即为有向无环图。[31]

举例来说，当电子表格中一个单元格的数值发生改变，其他直接或间接依赖于该单元格的所有单元格的值都需要被重新计算。被调度的任务为重新计算某个特定单元格的值。当一个单元格的值取决于另外一个单元格时，两个单元格之间则有依赖关系。每个被依赖单元格的值的计算过程都必须先于使用它的表达式执行。使用依赖图的拓扑排序来调度任务使得在每个单元格的值都仅被重新计算一次的情况下，整个工作表都能被更新。[32]相似的任务调度场景出现在程序源代码编译的makefile，[32]和优化计算机程序底层执行的指令调度中.[33]

一个有着五个里程碑（注有10–50）和六个任务（注有A–F）的计划评审图。ADF和BC是关键路径

计划评审技术是一种基于有向无环图的计划排定技术，通常用于组织大型的人工项目。在计划评审技术中，每个顶点表示项目的一个里程碑（英语：Milestone (project management)），每条有向边表示任务或者活动，连接着表示任务开始或结束的两个节点。每条边则被标注上预估需时。图中的最长路径即为项目的关键路径。关键路径决定了项目所需的总时间，里程碑的完成时间取决于结束于本顶点的最长路径。[34]

数据处理网络

有向无环图可以用于表示处理数据的元素网络。在网络中，数据从一个元素顶点的入边进入，处理后从出边离开。

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

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

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

因果结构

主条目：贝叶斯网络

系谱学和版本历史

托勒密王朝的谱系图。

谱系图可以看作是有向无环图，顶点代表家族成员，边代表亲子关系。[38]虽然谱系图也被称作为家族“树”, 但近亲结婚导致的血统崩溃（英语：pedigree collapse）会违反树的性质。即一个孩子的祖先既可以从父亲向上追溯，也可以从母亲一侧。[39]图中的母系血统和父系血统则可以看作为树。因为没有人可以是自己的祖先，谱系图是无环的。[40]

基于相同的原因， 一个分散式版本控制系统的版本历史的结构也是有向无环图。在系统中，每个版本对应一个节点。边连接起有直接衍生关系的两个版本。由于分支合并的存在，这个结构并不能用树来表示。[41]

在计算几何领域，许多随机化算法都会维护一个“历史有向无环图”，用以记录结构变动中的旧几何结构。例如，在德勞內三角化的随机增量算法中，在添加每个点时，通过用三个较小的三角形替换一个三角形，以及通过“翻转”操作将三角形对替换为另一对三角形，来改变三角剖分。在该算法的历史有向无环图中，每个在算法中构建出的三角形对应一个顶点，边则将每个三角形和替代它的两个或三个三角形连接起来。

参考文献

  1. ^ Introduction to Algorithms [算法导论]. : 1172. ISBN 978-7-111-40701-0. 
  2. ^ Thulasiraman, K.; Swamy, M. N. S., 5.7 Acyclic Directed Graphs, Graphs: Theory and Algorithms, John Wiley and Son: 118, 1992, ISBN 978-0-471-51356-8 .
  3. ^ 3.0 3.1 Bang-Jensen, Jørgen, 2.1 Acyclic Digraphs, Digraphs: Theory, Algorithms and Applications, Springer Monographs in Mathematics 2nd, Springer-Verlag: 32–34, 2008, ISBN 978-1-84800-997-4 .
  4. ^ Christofides, Nicos, Graph theory: an algorithmic approach, Academic Press: 170–174, 1975 .
  5. ^ Mitrani, I., Simulation Techniques for Discrete Event Systems, Cambridge Computer Science Texts 14, Cambridge University Press: 27, 1982, ISBN 9780521282826 .
  6. ^ Kozen, Dexter, The Design and Analysis of Algorithms, Monographs in Computer Science, Springer: 9, 1992, ISBN 978-0-387-97687-7 .
  7. ^ Banerjee, Utpal, Exercise 2(c), Loop Transformations for Restructuring Compilers: The Foundations, Springer: 19, 1993, ISBN 978-0-7923-9318-4 .
  8. ^ Bang-Jensen, Jørgen; Gutin, Gregory Z., 2.3 Transitive Digraphs, Transitive Closures and Reductions, Digraphs: Theory, Algorithms and Applications, Springer Monographs in Mathematics, Springer: 36–39, 2008, ISBN 978-1-84800-998-1 .
  9. ^ Jungnickel, Dieter, Graphs, Networks and Algorithms, Algorithms and Computation in Mathematics 5, Springer: 92–93, 2012, ISBN 978-3-642-32278-5 .
  10. ^ Sedgewick, Robert; Wayne, Kevin, 4,2,25 Unique topological ordering, Algorithms 4th, Addison-Wesley: 598–599, 2011, ISBN 978-0-13-276256-4 .
  11. ^ Bender, Edward A.; Williamson, S. Gill, Example 26 (Linear extensions – topological sorts), A Short Course in Discrete Mathematics, Dover Books on Computer Science, Courier Dover Publications: 142, 2005, ISBN 978-0-486-43946-4 .
  12. ^ 12.0 12.1 Robinson, R. W., Counting labeled acyclic digraphs, Harary, F. (编), New Directions in the Theory of Graphs, Academic Press: 239–273, 1973 . See also Harary, Frank; Palmer, Edgar M., Graphical Enumeration, Academic Press: 19, 1973, ISBN 978-0-12-324245-7 .
  13. ^ 埃里克·韦斯坦因. Weisstein's Conjecture. MathWorld. 
  14. ^ McKay, B. D.; Royle, G. F.; Wanless, I. M.; Oggier, F. E.; Sloane, N. J. A.; Wilf, H., Acyclic digraphs and eigenvalues of (0,1)-matrices, Journal of Integer Sequences, 2004, 7 , Article 04.3.3.
  15. ^ Rebane, George; Pearl, Judea, The recovery of causal poly-trees from statistical data, in Proc. 3rd Annual Conference on Uncertainty in Artificial Intelligence (UAI 1987), Seattle, WA, USA, July 1987 (PDF): 222–228, 1987 [永久失效連結].
  16. ^ Furnas, George W.; Zacks, Jeff, Multitrees: enriching and reusing hierarchical structure, Proc. SIGCHI conference on Human Factors in Computing Systems (CHI '94): 330–336, 1994, ISBN 978-0897916509, doi:10.1145/191666.191778 .
  17. ^ 17.0 17.1 Cormen, Thomas H. （英语：Thomas H. Cormen）; Leiserson, Charles E. （英语：Charles E. Leiserson）; Rivest, Ronald L.; Stein, Clifford. Introduction to Algorithms 2nd. MIT Press and McGraw-Hill. 2001 [1990]. ISBN 0-262-03293-7.  Section 22.4, Topological sort, pp. 549–552.
  18. ^ 18.0 18.1 Jungnickel (2012), pp. 50–51.
  19. ^ For depth-first search based topological sorting algorithm, this validity check can be interleaved with the topological sorting algorithm itself; see e.g. Skiena, Steven S., The Algorithm Design Manual, Springer: 179–181, 2009, ISBN 978-1-84800-070-4 .
  20. ^ Stanley, Richard P., Acyclic orientations of graphs (PDF), Discrete Mathematics, 1973, 5 (2): 171–178, doi:10.1016/0012-365X(73)90108-8 .
  21. ^ Garey, Michael R.; Johnson, David S., Problems GT7 and GT8, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman: 191–192, 1979, ISBN 0-7167-1045-5 
  22. ^ Harary, Frank; Norman, Robert Z.; Cartwright, Dorwin, Structural Models: An Introduction to the Theory of Directed Graphs, John Wiley & Sons: 63, 1965 .
  23. ^ Skiena (2009), p. 495.
  24. ^ Skiena (2009), p. 496.
  25. ^ Bang-Jensen & Gutin (2008), p. 38.
  26. ^ Picard, Jean-Claude, Maximal closure of a graph and applications to combinatorial problems, Management Science（英语：Management Science (journal)）, 1976, 22 (11): 1268–1272, MR 0403596, doi:10.1287/mnsc.22.11.1268 .
  27. ^ Cormen et al. 2001, Section 24.2, Single-source shortest paths in directed acyclic graphs, pp. 592–595.
  28. ^ Cormen et al. 2001, Sections 24.1, The Bellman–Ford algorithm, pp. 588–592, and 24.3, Dijkstra's algorithm, pp. 595–601.
  29. ^ Cormen et al. 2001, p. 966.
  30. ^ Skiena (2009), p. 469.
  31. ^ Al-Mutawa, H. A.; Dietrich, J.; Marsland, S.; McCartin, C., On the shape of circular dependencies in Java programs, 23rd Australian Software Engineering Conference, IEEE: 48–57, 2014, ISBN 978-1-4799-3149-1, doi:10.1109/ASWEC.2014.15 .
  32. ^ 32.0 32.1 Gross, Jonathan L.; Yellen, Jay; Zhang, Ping, Handbook of Graph Theory 2nd, CRC Press: 1181, 2013, ISBN 978-1-4398-8018-0 .
  33. ^ Srikant, Y. N.; Shankar, Priti, The Compiler Design Handbook: Optimizations and Machine Code Generation 2nd, CRC Press: 19–39, 2007, ISBN 978-1-4200-4383-9 .
  34. ^ Wang, John X., What Every Engineer Should Know About Decision Making Under Uncertainty, CRC Press: 160, 2002, ISBN 978-0-8247-4373-4 .
  35. ^ Sapatnekar, Sachin, Timing, Springer: 133, 2004, ISBN 978-1-4020-7671-8 .
  36. ^ Dennis, Jack B., First version of a data flow procedure language, Programming Symposium, Lecture Notes in Computer Science 19: 362–376, 1974, ISBN 978-3-540-06859-4, doi:10.1007/3-540-06859-7_145 .
  37. ^ Touati, Sid; de Dinechin, Benoit, Advanced Backend Optimization, John Wiley & Sons: 123, 2014, ISBN 978-1-118-64894-0 .
  38. ^ Kirkpatrick, Bonnie B., Haplotypes versus genotypes on pedigrees, Algorithms for Molecular Biology, April 2011, 6 (10): 10, PMC 3102622 可免费查阅, PMID 21504603, doi:10.1186/1748-7188-6-10 .
  39. ^ McGuffin, M. J.; Balakrishnan, R., Interactive visualization of genealogical graphs (PDF), IEEE Symposium on Information Visualization (INFOVIS 2005): 16–23, 2005, ISBN 978-0-7803-9464-3, doi:10.1109/INFVIS.2005.1532124 .
  40. ^ Bender, Michael A.; Pemmasani, Giridhar; Skiena, Steven; Sumazin, Pavel, Finding least common ancestors in directed acyclic graphs, Proceedings of the Twelfth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA '01), Philadelphia, PA, USA: Society for Industrial and Applied Mathematics: 845–854, 2001, ISBN 978-0-89871-490-6 .
  41. ^ Bartlang, Udo, Architecture and Methods for Flexible Content Management in Peer-to-Peer Systems, Springer: 59, 2010, ISBN 978-3-8348-9645-2 .
检索自“https://zh.wikipedia.org/w/index.php?title=有向无环图&oldid=59896021”