一個有向無環圖的例子 在图论 中，如果一个有向图 从任意顶点 出发无法经过若干条边 回到该点 ，则这个图是一个有向无环图 （英語：Directed Acyclic Graph ，縮寫：DAG ）。[ 1]
因为有向无环图中从一个点到另一个点有可能存在两种路线，因此有向无环图未必能转化成树，但任何有向树均为有向无环图。
图 由顶点 和连接这些顶点的边 所构成。每条边都带有从一个顶点指向另一个顶点的方向的图为有向图 。有向图中的道路 为一系列的边，系列中每条边的终点都是下一条边的起点。如果一条路径的起点是这条路径的终点，那么这条路径就是一个环。有向无环图即为没有环出现的有向图。[ 2] [ 3] [ 4]
在以蓝线标识的有向无环图中，添加红线从而得到其传递闭包 当存在一条从顶点u v v u 可达 [ 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 u v u → v [ 8]
将{ x, y, z }的幂集 按包含 偏序排序得到的哈斯图 对于有向无环图G ≤ G 覆盖关系 G 绘图 。偏序关系的哈斯图 由将传递规约中的每条边的起点绘制在其终点的下方而得到。[ 9]
有向无环图的拓扑排序 为所有边的起点都出现在其终点之前的排序。能构成拓扑排序的图一定没有环，因为环中的一条边必定从排序较后的顶点指向比其排序更前的顶点。[ 3] [ 10]
有向无环图的拓扑排序族等同于其可达性的线性拓展 [ 11]
罗宾逊 (1973) harvtxt模板錯誤: 無指向目標: CITEREF罗宾逊1973 (幫助 ) 研究了有向无环图的图计数 [ 12] n
1, 1, 3, 25, 543, 29281, 3781503, … （OEIS 數列A003024 ）。 其中n = 0, 1, 2, 3,……递推关系式 是
a
n
=
∑
k
=
1
n
(
−
1
)
k
−
1
(
n
k
)
2
k
(
n
−
k
)
a
n
−
k
.
{\displaystyle a_{n}=\sum _{k=1}^{n}(-1)^{k-1}{n \choose k}2^{k(n-k)}a_{n-k}.}
[ 12] 埃里克·韦斯坦因 推测[ 13] n 特征值 都为正实数的n*n 逻辑矩阵 的数量相同。这一点随后被证实，证明采用了双射法 ：一个矩阵A 邻接矩阵 ，当且仅当A + I I 单位矩阵 。因为一个有向无环图不允许自环 ，它的邻接矩阵的对角线必定全为0。因此，加上I [ 14]
多重树 自由树 的边定向 [ 15] 树状图 。
强明确树 v v [ 16]
可以用线性时间复杂度 的卡恩算法来找到一个有向无环图的拓扑排序。[ 17] L L L L [ 18] 深度优先搜索 的后序遍历 结果翻转。[ 17]
检查一个有向图是否为有向无环图亦可在线性时间内完成。一种方法是先找到一个拓扑排序，然后测试这个排序是否能符合图中每条边所连顶点在排序中应该出现的顺序。[ 19] [ 18] L
任意无向图都可以被转化为有向无环图。构造方法是选定一个顶点的全序关系 ，并将无向图中所有边从全序关系中较前的顶点指向较后的顶点。这种方法是定向 无环定向 n n !χ 色多项式 ，无环定向数量等于|χ (−1)| [ 20]
任意有环有向图都可以被转化为有向无环图。只要从图中移除反馈节点集 反馈边集 NP困难 问题。[ 21] 收缩 为一个顶点。[ 22] 空集 ，它的强连通分量则为自身。
有向无环图的传递闭包可以通过广度优先搜索 或深度优先搜索 对每个节点测试可达性来构建。算法对于一个有着n m O (mn )[ 23] 矩阵乘法算法 Coppersmith–Winograd算法 O (n 2.3728639 稠密图 O (mn )[ 24]
不论在哪种传递闭包算法中，那些被一条长度至少为2的路径所连接的顶点对，都可以和只有一条长度为1的路径所连接的顶点对区分开。由于传递约简包含后者，传递约简可以在和传递闭包相同的渐进时间复杂度 [ 25]
闭包是一个图中没有出边的顶点子集，即不存在从子集中顶点指向子集外顶点的边。闭包问题 最大流问题 的简化版，在多项式时间 内被解决。实际上，是否有环对于找到闭包没有影响。[ 26]
基于拓扑排序的性质，有向无环图的最短路问题 和最长路径问题 可以在线性时间内解决。将顶点拓扑排序后，从前到后遍历每一个顶点，对于遍历到的顶点，更新其所有出边所到达顶点的长度值。如果求最短路，则在本边是更短路径的一部分时更新。求最长路则反之。[ 27]
O
(
|
E
|
+
|
V
|
log
|
V
|
)
{\displaystyle O(|E|+|V|\log |V|)}
戴克斯特拉算法 或
O
(
|
V
|
|
E
|
)
{\displaystyle O(|V||E|)}
贝尔曼-福特算法 等。[ 28] NP困难问题 。[ 29]
有向无环图的偏序关系可以在调度 有着先后顺序限制的系统任务中发挥作用。[ 30] 電子試算表 中某个单元格的计算公式依赖于其他单元格，或在程序的源代码 被修改后重新编译目标文件 。依赖图 环状依赖 [ 31]
举例来说，当电子表格中一个单元格的数值发生改变，其他直接或间接依赖于该单元格的所有单元格的值都需要被重新计算。被调度的任务为重新计算某个特定单元格的值。当一个单元格的值取决于另外一个单元格时，两个单元格之间则有依赖关系。每个被依赖单元格的值的计算过程都必须先于使用它的表达式执行。使用依赖图的拓扑排序来调度任务使得在每个单元格的值都仅被重新计算一次的情况下，整个工作表都能被更新。[ 32] makefile [ 32] 指令调度 中。[ 33]
一个有着五个里程碑（注有10–50）和六个任务（注有A–F）的计划评审图。ADF和BC是关键路径 计划评审技术 是一种基于有向无环图的计划排定技术，通常用于组织大型的人工项目。在计划评审技术中，每个顶点表示项目的一个里程碑 最长路径 即为项目的关键路径 。关键路径决定了项目所需的总时间，里程碑的完成时间取决于结束于本顶点的最长路径。[ 34]
有向无环图可以用于表示处理数据的元素网络。在网络中，数据从一个元素顶点的入边进入，处理后从出边离开。
在电子电路设计中，静态组合逻辑电路 块可以被表示为由邏輯閘 组成的有向无环系统。每个逻辑门对输入做一次函数处理，输入和输出均为一个位元 组。通常，这些电路块的输出不能够再作为输入，除非它们被存储在寄存器或者状态单元中，以保证图不出现环。[ 35]
数据式编程 数据流 并发 执行，从而高效利用多核心处理器 。[ 36]
在編譯器 中，直线码（不含条件分支和循环的代码段）可以使用有向无环图表示。图标示出每个算术运算的输入和输出。这种表示法让编译器能执行通用子表达式删除 [ 37]
用顶点表示事件，边表示因果关系 的图通常是无环的。[ 38]
举例来说，貝氏網路 表示多个概率事件的关联网络。顶点表示事件，后续事件的发生可能性则可以通过其在有向无环图的前驱节点的发生概率计算出来。[ 39] 端正图 [ 40]
另外一种具有相似因果结构的图是影响图 [ 41] 流行病学 中，这些表示因果关系的图表常常用来评估不同干预手段的效果。[ 42] [ 43]
托勒密王朝 的谱系图。谱系图 可以看作是有向无环图，顶点代表家族成员，边代表亲子关系。[ 44] 血统崩溃 [ 45] 母系血统 和父系血统 则可以看作为树。因为没有人可以是自己的祖先，谱系图是无环的。[ 46]
基于相同的原因， 一个分散式版本控制 系统的版本历史的结构也是有向无环图。在系统中，每个版本对应一个节点。边连接起有直接衍生关系的两个版本。由于分支合并的存在，这个结构并不能用树来表示。[ 47]
在计算几何 领域，许多随机化算法都会维护一个“历史有向无环图”，用以记录结构变动中的旧几何结构。例如，在德勞內三角化 的随机增量算法中，在添加每个点时，通过用三个较小的三角形替换一个三角形，以及通过“翻转”操作将三角形对替换为另一对三角形，来改变三角剖分。在该算法的历史有向无环图中，每个在算法中构建出的三角形对应一个顶点，边则将每个三角形和替代它的两个或三个三角形连接起来。这种图结构可以高效地处理点定位 q q q 的德劳内三角形。[ 48]
在引用图 引用 关系。1965年普莱斯 的文章“科学文献的网络”是使用引用图的一个经典例子。[ 49] 引用次数 引文分析 中的一种重要的展示方式。另一个例子是法律裁判 中，法官通过引用过往案例中的判决来支持他们的结论。引用图亦可以用来描绘专利 ，因为专利必须要提及现有技术 ，即已经公开的并且和本专利有关的先前专利。
相较于网络科学 中对一般图的研究，有向无环图的独特性质可以被用来作深层次分析。例如，传递规约可以呈现引用在不同应用领域的分布情况，这突出了不同领域中不同的引用网构造机制。[ 50] 主干道路分析
分别用trie（左）和有向无环词图（右）存放英文单词“tap”，“taps”，“top”和“tops”。EOW 表示单词结束。 有向无环图也可以用于对一系列序列的压缩 中。在这里，有向无环图中的路径代表这些序列。当多个序列有共同的子序列时，子序列可以被表示为这些序列对应路径的公共边。比起直接列出所有序列，这种方法占用更少空间。例如，有向无环词图 字符串 ，字符串可以是英文单词。[ 51] trie 。相比于trie，有向无环词图允许多条边指向同一个顶点，使得具有相同后缀的一些词的词头可以被相同的顶点所表示，因而更省空间。[ 52]
二元决策图 是基于有向无环图的一种数据结构，用于表示布尔函数 [ 53] [ 54] 解释 的真值，只要从唯一的源顶点出发，沿着该顶点代表的布尔变量的实际真值所对应的出边一直前进，到达的汇则为其真值。如同有向无环词图可以被看作是trie的一种压缩形式一样，二元决策图可以被看作是决策树 的压缩形式。它通过将导向相同结果的边重新汇合到一个顶点来节省空间。[ 55]
^ Introduction to Algorithms [算法导论]. : 1172. ISBN 978-7-111-40701-0 ^ 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.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 ^ Christofides, Nicos , Graph theory: an algorithmic approach, Academic Press: 170–174, 1975 ^ Mitrani, I., Simulation Techniques for Discrete Event Systems , Cambridge Computer Science Texts 14 , Cambridge University Press: 27, 1982 [2020-01-18 ] , ISBN 9780521282826存档 于2021-03-10） ^ Kozen, Dexter , The Design and Analysis of Algorithms , Monographs in Computer Science, Springer: 9, 1992 [2020-01-14 ] , ISBN 978-0-387-97687-7存档 于2021-03-10） ^ Banerjee, Utpal, Exercise 2(c), Loop Transformations for Restructuring Compilers: The Foundations , Springer: 19, 1993 [2020-01-14 ] , ISBN 978-0-7923-9318-4存档 于2021-03-10） ^ 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 [2020-01-14 ] , ISBN 978-1-84800-998-1存档 于2021-03-10） ^ Jungnickel, Dieter, Graphs, Networks and Algorithms , Algorithms and Computation in Mathematics 5 , Springer: 92–93, 2012 [2020-01-15 ] , ISBN 978-3-642-32278-5存档 于2021-03-10） ^ Sedgewick, Robert ; Wayne, Kevin, 4,2,25 Unique topological ordering, Algorithms 4th, Addison-Wesley: 598–599, 2011 [2020-01-17 ] , ISBN 978-0-13-276256-4存档 于2021-03-10） ^ 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 [2020-01-17 ] , ISBN 978-0-486-43946-4存档 于2021-03-10） ^ 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 Harary, Frank ; Palmer, Edgar M., Graphical Enumeration, Academic Press : 19, 1973, ISBN 978-0-12-324245-7 ^ Weisstein, Eric W. (编). Weisstein's Conjecture . at MathWorld Wolfram Research, Inc. （英语） . ^ 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 [2020-01-19 ] , （原始内容存档 于2021-02-24） ^ 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 [永久失效連結 ^ 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-0897916509doi:10.1145/191666.191778 ^ 17.0 17.1 Cormen, Thomas H. Leiserson, Charles E. Rivest, Ronald L. ; Stein, Clifford . Introduction to Algorithms 2nd. MIT Press and McGraw-Hill. 2001 [1990]. ISBN 0-262-03293-7 ^ 18.0 18.1 Jungnickel (2012) , pp. 50–51.^ 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 [2020-01-21 ] , ISBN 978-1-84800-070-4存档 于2021-03-10）
^ Stanley, Richard P. , Acyclic orientations of graphs (PDF) , Discrete Mathematics, 1973, 5 (2): 171–178 [2020-01-22 ] , doi:10.1016/0012-365X(73)90108-8 存档 (PDF) 于2021-02-24） ^ 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 ^ Harary, Frank ; Norman, Robert Z.; Cartwright, Dorwin, Structural Models: An Introduction to the Theory of Directed Graphs, John Wiley & Sons: 63, 1965 ^ Skiena (2009) , p. 495.^ Skiena (2009) , p. 496.^ Bang-Jensen & Gutin (2008) , p. 38.^ Picard, Jean-Claude, Maximal closure of a graph and applications to combinatorial problems, Management Science 22 (11): 1268–1272, MR 0403596 doi:10.1287/mnsc.22.11.1268 ^ Cormen et al. 2001, Section 24.2, Single-source shortest paths in directed acyclic graphs, pp. 592–595.
^ Cormen et al. 2001, Sections 24.1, The Bellman–Ford algorithm, pp. 588–592, and 24.3, Dijkstra's algorithm, pp. 595–601.
^ Cormen et al. 2001, p. 966.
^ Skiena (2009) , p. 469.^ 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-1doi:10.1109/ASWEC.2014.15 ^ 32.0 32.1 Gross, Jonathan L.; Yellen, Jay; Zhang, Ping , Handbook of Graph Theory 2nd, CRC Press: 1181, 2013 [2020-01-30 ] , ISBN 978-1-4398-8018-0存档 于2021-03-10） ^ Srikant, Y. N.; Shankar, Priti, The Compiler Design Handbook: Optimizations and Machine Code Generation 2nd, CRC Press: 19–39, 2007 [2020-01-30 ] , ISBN 978-1-4200-4383-9存档 于2021-03-10） ^ Wang, John X., What Every Engineer Should Know About Decision Making Under Uncertainty , CRC Press: 160, 2002 [2020-01-31 ] , ISBN 978-0-8247-4373-4存档 于2021-03-10） ^ Sapatnekar, Sachin, Timing , Springer: 133, 2004 [2020-02-03 ] , ISBN 978-1-4020-7671-8存档 于2021-03-10） ^ 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-4doi:10.1007/3-540-06859-7_145 ^ Touati, Sid; de Dinechin, Benoit, Advanced Backend Optimization , John Wiley & Sons: 123, 2014 [2020-02-04 ] , ISBN 978-1-118-64894-0存档 于2021-03-10） ^ Gopnik, Alison; Schulz, Laura, Causal Learning , Oxford University Press: 4, 2007 [2020-06-01 ] , ISBN 978-0-19-803928-0存档 于2021-03-10） ^ Shmulevich, Ilya; Dougherty, Edward R., Probabilistic Boolean Networks: The Modeling and Control of Gene Regulatory Networks , Society for Industrial and Applied Mathematics: 58, 2010 [2020-06-01 ] , ISBN 978-0-89871-692-4存档 于2021-03-10） ^ Cowell, Robert G.; Dawid, A. Philip ; Lauritzen, Steffen L. ; Spiegelhalter, David J. , 3.2.1 Moralization, Probabilistic Networks and Expert Systems, Springer: 31–33, 1999, ISBN 0-387-98767-3 ^ Dorf, Richard C., The Technology Management Handbook , CRC Press: 9-7, 1998 [2020-06-01 ] , ISBN 978-0-8493-8577-3存档 于2021-03-10） ^ Boslaugh, Sarah, Encyclopedia of Epidemiology, Volume 1 , SAGE: 255, 2008 [2020-06-01 ] , ISBN 978-1-4129-2816-8存档 于2021-03-10） ^ Pearl, Judea . Causal diagrams for empirical research . Biometrika. 1995, 82 (4): 669–709. doi:10.1093/biomet/82.4.669 ^ 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 ^ McGuffin, M. J.; Balakrishnan, R., Interactive visualization of genealogical graphs (PDF) , IEEE Symposium on Information Visualization (INFOVIS 2005): 16–23, 2005 [2020-02-07 ] , ISBN 978-0-7803-9464-3doi:10.1109/INFVIS.2005.1532124 存档 (PDF) 于2021-02-24） ^ 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 [2020-02-08 ] , ISBN 978-0-89871-490-6存档 于2018-12-01） ^ Bartlang, Udo, Architecture and Methods for Flexible Content Management in Peer-to-Peer Systems , Springer: 59, 2010 [2020-05-31 ] , ISBN 978-3-8348-9645-2存档 于2021-03-10） ^ Pach, János ; Sharir, Micha , Combinatorial Geometry and Its Algorithmic Applications: The Alcalá Lectures , Mathematical surveys and monographs 152 , American Mathematical Society: 93–94, [2020-06-01 ] , ISBN 978-0-8218-7533-9存档 于2021-03-10） ^ Price, Derek J. de Solla, Networks of Scientific Papers (PDF) , Science , July 30, 1965, 149 (3683): 510–515 [2020-06-01 ] , Bibcode:1965Sci...149..510D PMID 14325149 doi:10.1126/science.149.3683.510 存档 (PDF) 于2019-05-20） ^ Clough, James R.; Gollings, Jamie; Loach, Tamar V.; Evans, Tim S., Transitive reduction of citation networks, Journal of Complex Networks, 2015, 3 (2): 189–203, arXiv:1310.8224 doi:10.1093/comnet/cnu039 ^ Crochemore, Maxime; Vérin, Renaud, Direct construction of compact directed acyclic word graphs, Combinatorial Pattern Matching, Lecture Notes in Computer Science 1264 , Springer: 116–129, 1997, CiteSeerX 10.1.1.53.6273 ISBN 978-3-540-63220-7doi:10.1007/3-540-63220-4_55 ^ Lothaire, M. , Applied Combinatorics on Words , Encyclopedia of Mathematics and its Applications 105 , Cambridge University Press: 18, 2005 [2020-06-01 ] , ISBN 9780521848022存档 于2021-03-10） ^ Lee, C. Y., Representation of switching circuits by binary-decision programs, Bell System Technical Journal, 1959, 38 (4): 985–999, doi:10.1002/j.1538-7305.1959.tb01585.x ^ Akers, Sheldon B., Binary decision diagrams, IEEE Transactions on Computers, 1978, C–27 (6): 509–516, doi:10.1109/TC.1978.1675141 ^ Friedman, S. J.; Supowit, K. J., Finding the optimal variable ordering for binary decision diagrams, Proc. 24th ACM/IEEE Design Automation Conference (DAC '87), New York, NY, USA: ACM: 348–356, 1987, ISBN 978-0-8186-0781-3doi:10.1145/37888.37941
「DAG」重定向至此。关于其他用法，请见「DAG (消歧义)」。
