387
个编辑
更改
跳到导航
跳到搜索
第73行：
第73行： − + − − Family tree of the [[Ptolemaic dynasty, with many marriages between close relatives causing pedigree collapse]] − − − − − − Directed acyclic graphs representations of partial orderings have many applications in [[Schedule|scheduling]] for systems of tasks with ordering constraints.<ref>{{harvtxt|Skiena|2009}}, p. 469.</ref> − − Directed acyclic graphs representations of partial orderings have many applications in scheduling for systems of tasks with ordering constraints.[29] An important class of problems of this type concern collections of objects that need to be updated, such as the cells of a spreadsheet after one of the cells has been changed, or the object files of a piece of computer software after its source code has been changed. In this context, a dependency graph is a graph that has a vertex for each object to be updated, and an edge connecting two objects whenever one of them needs to be updated earlier than the other. A cycle in this graph is called a circular dependency, and is generally not allowed, because there would be no way to consistently schedule the tasks involved in the cycle. Dependency graphs without circular dependencies form DAGs.[30] − − For instance, when one cell of a spreadsheet changes, it is necessary to recalculate the values of other cells that depend directly or indirectly on the changed cell. For this problem, the tasks to be scheduled are the recalculations of the values of individual cells of the spreadsheet. Dependencies arise when an expression in one cell uses a value from another cell. In such a case, the value that is used must be recalculated earlier than the expression that uses it. Topologically ordering the dependency graph, and using this topological order to schedule the cell updates, allows the whole spreadsheet to be updated with only a single evaluation per cell.[31] Similar problems of task ordering arise in makefiles for program compilation[31] and instruction scheduling for low-level computer program optimization.[32] − − − A somewhat different DAG-based formulation of scheduling constraints is used by the [[program evaluation and review technique]] (PERT), a method for management of large human projects that was one of the first applications of DAGs. In this method, the vertices of a DAG represent [[Milestone (project management)|milestones]] of a project rather than specific tasks to be performed. Instead, a task or activity is represented by an edge of a DAG, connecting two milestones that mark the beginning and completion of the task. Each such edge is labeled with an estimate for the amount of time that it will take a team of workers to perform the task. The [[Longest path problem|longest path]] in this DAG represents the [[Critical path method|critical path]] of the project, the one that controls the total time for the project. Individual milestones can be scheduled according to the lengths of the longest paths ending at their vertices.<ref>{{citation |title=What Every Engineer Should Know About Decision Making Under Uncertainty |first=John X. |last=Wang |publisher=CRC Press |year=2002 |isbn=978-0-8247-4373-4 |page=160 |url=https://books.google.com/books?id=C3yKML0dUVIC&pg=PA160}}.</ref> − + − − the length of the longest path, from the n-th node added to the network to the first node in the network, scales as <math>\ln(n)</math>. − − 最长路径的长度，从添加到网络的第 n 个节点到网络中的第一个节点，缩放为 < math > ln (n) </math > 。 − − A directed acyclic graph may be used to represent a network of processing elements. In this representation, data enters a processing element through its incoming edges and leaves the element through its outgoing edges. − − 有向无环图可以用于表示处理数据的元素网络。在网络中，数据从一个元素顶点的入边进入，处理后从出边离开。 − − For instance, in electronic circuit design, static [[combinational logic]] blocks can be represented as an acyclic system of [[logic gate]]s that computes a function of an input, where the input and output of the function are represented as individual [[bit]]s. In general, the output of these blocks cannot be used as the input unless it is captured by a register or state element which maintains its acyclic properties.<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> Electronic circuit schematics either on paper or in a database are a form of directed acyclic graphs using instances or components to form a directed reference to a lower level component. Electronic circuits themselves are not necessarily acyclic or directed. − − − − [[Dataflow programming]] languages describe systems of operations on [[data stream]]s, and the connections between the outputs of some operations and the inputs of others. These languages can be convenient for describing repetitive data processing tasks, in which the same acyclically-connected collection of operations is applied to many data items. They can be executed as a [[parallel algorithm]] in which each operation is performed by a parallel process as soon as another set of inputs becomes available to it.<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> − − − The same idea of using a DAG to represent a family of paths occurs in the binary decision diagram, a DAG-based data structure for representing binary functions. In a binary decision diagram, each non-sink vertex is labeled by the name of a binary variable, and each sink and each edge is labeled by a 0 or 1. The function value for any truth assignment to the variables is the value at the sink found by following a path, starting from the single source vertex, that at each non-sink vertex follows the outgoing edge labeled with the value of that vertex's variable. Just as directed acyclic word graphs can be viewed as a compressed form of , binary decision diagrams can be viewed as compressed forms of decision trees that save space by allowing paths to rejoin when they agree on the results of all remaining decisions. − − − − In [[compiler]]s, straight line code (that is, sequences of statements without loops or conditional branches) may be represented by a DAG describing the inputs and outputs of each of the arithmetic operations performed within the code. This representation allows the compiler to perform [[common subexpression elimination]] efficiently.<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> At a higher level of code organization, the [[acyclic dependencies principle]] states that the dependencies between modules or components of a large software system should form a directed acyclic graph.<ref>{{citation|title=Large-Scale Software Architecture: A Practical Guide using UML|first1=Jeff|last1=Garland|first2=Richard|last2=Anthony|publisher=John Wiley & Sons|year=2003|isbn=9780470856383|page=215|url=https://books.google.com/books?id=_2oQLLSqZ88C&pg=PA215}}.</ref> − [[Feedforward neural network]]s are another example.+ − − − − {{main|Bayesian network}} − − Graphs in which vertices represent events occurring at a definite time, and where the edges are always point from the early time vertex to a late time vertex of the edge, are necessarily directed and acyclic. The lack of a cycle follows because the time associated with a vertex always increases as you follow any [[Path (graph theory)|path]] in the graph so you can never return to a vertex on a path. This reflects our natural intuition that causality means events can only affect the future, they never affect the past, and thus we have no [[causal loop]]s. An example of this type of directed acyclic graph are those encountered in the [[Causal sets|causal set approach to quantum gravity]] though in this case the graphs considered are [[#Transitive closure and transitive reduction|transitively complete]]. In the version history example, each version of the software is associated with a unique time, typically the time the version was saved, committed or released. For citation graphs, the documents are published at one time and can only refer to older documents. − − Sometimes events are not associated with a specific physical time. Provided that pairs of events have a purely causal relationship, that is edges represent [[causality|causal relations]] between the events, we will have a directed acyclic graph.<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=https://books.google.com/books?id=35MKXlKoXIUC&pg=PA4}}.</ref> For instance, a [[Bayesian network]] represents a system of probabilistic events as vertices in a directed acyclic graph, in which the likelihood of an event may be calculated from the likelihoods of its predecessors in the DAG.<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=https://books.google.com/books?id=RfshqEgO7KgC&pg=PA58}}.</ref> In this context, the [[moral graph]] of a DAG is the undirected graph created by adding an (undirected) edge between all parents of the same vertex (sometimes called ''marrying''), and then replacing all directed edges by undirected edges.<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= 978-0-387-98767-5 |chapter= 3.2.1 Moralization|pages= 31–33 }}.</ref> Another type of graph with a similar causal structure is an [[influence diagram]], the vertices of which represent either decisions to be made or unknown information, and the edges of which represent causal influences from one vertex to another.<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{{hyphen}}7<!-- Do not conver this hyphen into a dash! It is a section-page number, not a range of page numbers. -->|url=https://books.google.com/books?id=C2u8I0DFo4IC&pg=SA9-PA7}}.</ref> In [[epidemiology]], for instance, these diagrams are often used to estimate the expected value of different choices for intervention.<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=https://books.google.com/books?id=wObgnN3x14kC&pg=PA255}}.</ref><ref name="pearl:95">{{citation | last = Pearl | first = Judea | doi = 10.1093/biomet/82.4.669 | issue = 4 | journal = Biometrika | pages = 669–709 | title = Causal diagrams for empirical research | volume = 82 | year = 1995| url = https://escholarship.org/uc/item/6gv9n38c }}.</ref> − − Category:Directed graphs − − 类别: 有向图 − − − − Category:Directed acyclic graphs − − 范畴: 有向无圈图 − − The converse is also true. That is in any application represented by a directed acyclic graph there is a causal structure, either an explicit order or time in the example or an order which can be derived from graph structure. This follows because all directed acyclic graphs have a [[#Topological ordering|topological ordering]], i.e. there is at least one way to put the vertices in an order such that all edges point in the same direction along that order. − de:Graph (Graphentheorie)#Teilgraphen.2C Wege und Zyklen+ − − de:Graph (Graphentheorie)#Teilgraphen.2C Wege und Zyklen − − <noinclude> − − <small>This page was moved from [[wikipedia:en:Directed acyclic graph]]. Its edit history can be viewed at [[有向无环图/edithistory]]</small></noinclude> − − [[Category:待整理页面]] − − − − An important class of problems of this type concern collections of objects that need to be updated, such as the cells of a [[spreadsheet]] after one of the cells has been changed, or the [[object file]]s of a piece of computer software after its [[source code]] has been changed. − − In this context, a [[dependency graph]] is a graph that has a vertex for each object to be updated, and an edge connecting two objects whenever one of them needs to be updated earlier than the other. A cycle in this graph is called a [[circular dependency]], and is generally not allowed, because there would be no way to consistently schedule the tasks involved in the cycle. − − The version history of a distributed revision control system, such as Git, generally has the structure of a directed acyclic graph, in which there is a vertex for each revision and an edge connecting pairs of revisions that were directly derived from each other. These are not trees in general due to merges. − − Dependency graphs without circular dependencies form DAGs.<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 | s2cid=17570052 }}.</ref> − − − − In many randomized algorithms in computational geometry, the algorithm maintains a history DAG representing the version history of a geometric structure over the course of a sequence of changes to the structure. For instance in a randomized incremental algorithm for Delaunay triangulation, the triangulation changes by replacing one triangle by three smaller triangles when each point is added, and by "flip" operations that replace pairs of triangles by a different pair of triangles. The history DAG for this algorithm has a vertex for each triangle constructed as part of the algorithm, and edges from each triangle to the two or three other triangles that replace it. This structure allows point location queries to be answered efficiently: to find the location of a query point in the Delaunay triangulation, follow a path in the history DAG, at each step moving to the replacement triangle that contains . The final triangle reached in this path must be the Delaunay triangle that contains . − − For instance, when one cell of a [[spreadsheet]] changes, it is necessary to recalculate the values of other cells that depend directly or indirectly on the changed cell. For this problem, the tasks to be scheduled are the recalculations of the values of individual cells of the spreadsheet. Dependencies arise when an expression in one cell uses a value from another cell. In such a case, the value that is used must be recalculated earlier than the expression that uses it. Topologically ordering the dependency graph, and using this topological order to schedule the cell updates, allows the whole spreadsheet to be updated with only a single evaluation per cell.<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> Similar problems of task ordering arise in [[makefile]]s for program compilation<ref name="hgt1181" /> and [[instruction scheduling]] for low-level computer program optimization.<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> − − The converse is also true. That is in any application represented by a directed acyclic graph there is a causal structure, either an explicit order or time in the example or an order which can be derived from graph structure. This follows because all directed acyclic graphs have a topological ordering, i.e. there is at least one way to put the vertices in an order such that all edges point in the same direction along that order. − + − [[File:Pert chart colored.svg|thumb|PERT chart for a project with five milestones (labeled 10–50) and six tasks (labeled A–F). There are two critical paths, ADF and BC.]] − − − In a citation graph the vertices are documents with a single publication date. The edges represent the citations from the bibliography of one document to other necessarily earlier documents. The classic example comes from the citations between academic papers as pointed out in the 1965 article "Networks of Scientific Papers" by Derek J. de Solla Price who went on to produce the first model of a citation network, the Price model. In this case the citation count of a paper is just the in-degree of the corresponding vertex of the citation network. This is an important measure in citation analysis. Court judgements provide another example as judges support their conclusions in one case by recalling other earlier decisions made in previous cases. A final example is provided by patents which must refer to earlier prior art, earlier patents which are relevant to the current patent claim. By taking the special properties of directed acyclic graphs into account, one can analyse citation networks with techniques not available when analysing the general graphs considered in many studies using network analysis. For instance transitive reduction gives a new insights into the citation distributions found in different applications highlighting clear differences in the mechanisms creating citations networks in different contexts. Another technique is main path analysis, which traces the citation links and suggests the most significant citation chains in a given citation graph. − − − The Price model is too simple to be a realistic model of a citation network but it is simple enough to allow for analytic solutions for some of its properties. Many of these can be found by using results derived from the undirected version of the Price model, the Barabási–Albert model. However, since Price's model gives a directed acyclic graph, it is a useful model when looking for analytic calculations of properties unique to directed acyclic graphs. For instance, 第209行：
第120行： − + − Directed acyclic graphs may also be used as a compact representation of a collection of sequences. In this type of application, one finds a DAG in which the paths form the given sequences. When many of the sequences share the same subsequences, these shared subsequences can be represented by a shared part of the DAG, allowing the representation to use less space than it would take to list out all of the sequences separately. For example, the directed acyclic word graph is a data structure in computer science formed by a directed acyclic graph with a single source and with edges labeled by letters or symbols; the paths from the source to the sinks in this graph represent a set of strings, such as English words.[53] Any set of sequences can be represented as paths in a tree, by forming a tree vertex for every prefix of a sequence and making the parent of one of these vertices represent the sequence with one fewer element; the tree formed in this way for a set of strings is called a trie. A directed acyclic word graph saves space over a trie by allowing paths to diverge and rejoin, so that a set of words with the same possible suffixes can be represented by a single tree vertex.[54] − − The same idea of using a DAG to represent a family of paths occurs in the binary decision diagram,[55][56] a DAG-based data structure for representing binary functions. In a binary decision diagram, each non-sink vertex is labeled by the name of a binary variable, and each sink and each edge is labeled by a 0 or 1. The function value for any truth assignment to the variables is the value at the sink found by following a path, starting from the single source vertex, that at each non-sink vertex follows the outgoing edge labeled with the value of that vertex's variable. Just as directed acyclic word graphs can be viewed as a compressed form of tries, binary decision diagrams can be viewed as compressed forms of decision trees that save space by allowing paths to rejoin when they agree on the results of all remaining decisions.[57]
→Applications 应用
== Applications 应用 ==
== Applications 应用 ==
=== 调度 ===
=== Scheduling 调度 ===
有向无环图的偏序关系可以在调度有着先后顺序限制的系统任务中发挥作用。[29]调度问题的一个重要种类是串联需要更新的对象，如電子試算表中某个单元格的计算公式依赖于其他单元格，或在程序的源代码被修改后重新编译目标文件。依赖图（英语：dependency graph）则记录了这种更新依赖关系。其每个顶点对应一个需要被更新的对象，边则表示更新的关系。依赖图中的环被称为环状依赖（英语：circular dependency）。环状依赖通常是不被允许出现的，因为不能保证圈内任务排定顺序的一致性。无环的依赖图即为有向无环图。[31]
有向无环图的偏序关系可以在调度有着先后顺序限制的系统任务中发挥作用。[29]调度问题的一个重要种类是串联需要更新的对象，如電子試算表中某个单元格的计算公式依赖于其他单元格，或在程序的源代码被修改后重新编译目标文件。依赖图（英语：dependency graph）则记录了这种更新依赖关系。其每个顶点对应一个需要被更新的对象，边则表示更新的关系。依赖图中的环被称为环状依赖（英语：circular dependency）。环状依赖通常是不被允许出现的，因为不能保证圈内任务排定顺序的一致性。无环的依赖图即为有向无环图。[31]
举例来说，当电子表格中一个单元格的数值发生改变，其他直接或间接依赖于该单元格的所有单元格的值都需要被重新计算。被调度的任务为重新计算某个特定单元格的值。当一个单元格的值取决于另外一个单元格时，两个单元格之间则有依赖关系。每个被依赖单元格的值的计算过程都必须先于使用它的表达式执行。使用依赖图的拓扑排序来调度任务使得在每个单元格的值都仅被重新计算一次的情况下，整个工作表都能被更新。[31]相似的任务调度场景出现在程序源代码编译的makefile，[31]和优化计算机程序底层执行的指令调度中。[32]
举例来说，当电子表格中一个单元格的数值发生改变，其他直接或间接依赖于该单元格的所有单元格的值都需要被重新计算。被调度的任务为重新计算某个特定单元格的值。当一个单元格的值取决于另外一个单元格时，两个单元格之间则有依赖关系。每个被依赖单元格的值的计算过程都必须先于使用它的表达式执行。使用依赖图的拓扑排序来调度任务使得在每个单元格的值都仅被重新计算一次的情况下，整个工作表都能被更新。[31]相似的任务调度场景出现在程序源代码编译的makefile，[31]和优化计算机程序底层执行的指令调度中。[32]
计划评审技术是一种基于有向无环图的计划排定技术，通常用于组织大型的人工项目。在计划评审技术中，每个顶点表示项目的一个里程碑（英语：Milestone (project management)），每条有向边表示任务或者活动，连接着表示任务开始或结束的两个节点。每条边则被标注上预估需时。图中的最长路径即为项目的关键路径。关键路径决定了项目所需的总时间，里程碑的完成时间取决于结束于本顶点的最长路径。[33]
计划评审技术是一种基于有向无环图的计划排定技术，通常用于组织大型的人工项目。在计划评审技术中，每个顶点表示项目的一个里程碑（英语：Milestone (project management)），每条有向边表示任务或者活动，连接着表示任务开始或结束的两个节点。每条边则被标注上预估需时。图中的最长路径即为项目的关键路径。关键路径决定了项目所需的总时间，里程碑的完成时间取决于结束于本顶点的最长路径。[33]
=== Data processing networks 数据处理网络===
=== 数据处理网络===
在电子电路设计中，静态组合逻辑电路块可以被表示为由逻辑门组成的有向无环系统。每个逻辑门对输入做一次函数处理，输入和输出均为一个位元组。通常，这些电路块的输出不能够再作为输入，除非它们被存储在寄存器或者状态单元中，以保证图不出现环。[35]纸上或数据库中的电子电路原理图是一种有向无环图的形式，它使用实例或元件来形成对低级元件的有向引用。电子电路本身不一定是非循环的或定向的。
在电子电路设计中，静态组合逻辑电路块可以被表示为由逻辑门组成的有向无环系统。每个逻辑门对输入做一次函数处理，输入和输出均为一个位元组。通常，这些电路块的输出不能够再作为输入，除非它们被存储在寄存器或者状态单元中，以保证图不出现环。[35]纸上或数据库中的电子电路原理图是一种有向无环图的形式，它使用实例或元件来形成对低级元件的有向引用。电子电路本身不一定是非循环的或定向的。
数据式编程（英语：Dataflow programming）语言描述针对数据流（英语：data stream）的操作，以及操作的输出和其他操作的输入之间的关系。这类型的语言使得描绘高重复率数据处理任务的变得更加简单，因为同样的数据操作可以应用于许多数据项。数据操作可以用有向无环图来表示。这些数据操作可以被并发执行，其中每一个操作都是在另一组输入可用时由一个并行进程来执行的，从而高效利用多核心处理器。[35]
数据式编程（英语：Dataflow programming）语言描述针对数据流（英语：data stream）的操作，以及操作的输出和其他操作的输入之间的关系。这类型的语言使得描绘高重复率数据处理任务的变得更加简单，因为同样的数据操作可以应用于许多数据项。数据操作可以用有向无环图来表示。这些数据操作可以被并发执行，其中每一个操作都是在另一组输入可用时由一个并行进程来执行的，从而高效利用多核心处理器。[35]
使用 DAG 表示一系列路径的同样想法也出现在二元决策图中，这是一个基于 dags 的数据结构，用于表示二进制函数。在二元决策图中，每个无汇点都用一个二进制变量的名称标记，每个汇点和每条边都用一个0或1标记。任何对变量进行真值赋值的函数值，都是指从单个源顶点开始，沿着一条路径，在每个非汇顶点上沿着标有该顶点变量值的外向边缘，在汇处找到的值。正如有向无环字图可以看作是一种压缩形式，二叉决策图可以看作是一种压缩形式的决策树，通过允许路径在所有剩余决策的结果一致时重新连接来节省空间。
使用 DAG 表示一系列路径的同样想法也出现在二元决策图中，这是一个基于 dags 的数据结构，用于表示二进制函数。在二元决策图中，每个无汇点都用一个二进制变量的名称标记，每个汇点和每条边都用一个0或1标记。任何对变量进行真值赋值的函数值，都是指从单个源顶点开始，沿着一条路径，在每个非汇顶点上沿着标有该顶点变量值的外向边缘，在汇处找到的值。正如有向无环字图可以看作是一种压缩形式，二叉决策图可以看作是一种压缩形式的决策树，通过允许路径在所有剩余决策的结果一致时重新连接来节省空间。
在编译器中，直线码（不含条件分支和循环的代码段）可以使用有向无环图表示。图标示出每个算术运算的输入和输出。这种表示法让编译器能执行通用子表达式删除（英语：common subexpression elimination），使得代码更高效。在更高级别的代码组织中，非循环依赖性原则指出，大型软件系统的模块或组件之间的依赖关系应形成一个有向非循环图。[37]
在编译器中，直线码（不含条件分支和循环的代码段）可以使用有向无环图表示。图标示出每个算术运算的输入和输出。这种表示法让编译器能执行通用子表达式删除（英语：common subexpression elimination），使得代码更高效。在更高级别的代码组织中，非循环依赖性原则指出，大型软件系统的模块或组件之间的依赖关系应形成一个有向非循环图。[37]
=== 因果结构 ===
=== Causal structures 因果结构 ===
用顶点表示事件，边表示因果关系的图通常是无环的。[38]事件由时间上的先后顺序来排列，所有箭头遵循从先发生事件指向后发生事件的原则，因此也不存在环。
用顶点表示事件，边表示因果关系的图通常是无环的。[38]事件由时间上的先后顺序来排列，所有箭头遵循从先发生事件指向后发生事件的原则，因此也不存在环。
这类有向无环图的一个例子是在量子引力的因果集方法中遇到的那些图，尽管在这种情况下所考虑的图是传递完全的。在版本历史示例中，软件的每个版本都与一个唯一的时间相关联，通常是保存、提交或发布版本的时间。对于引文图表，文档一次发布，只能引用较旧的文档。
这类有向无环图的一个例子是在量子引力的因果集方法中遇到的那些图，尽管在这种情况下所考虑的图是传递完全的。在版本历史示例中，软件的每个版本都与一个唯一的时间相关联，通常是保存、提交或发布版本的时间。对于引文图表，文档一次发布，只能引用较旧的文档。
反之亦然。也就是说，在由有向无环图表示的任何应用程序中，都有一个因果结构，或者是示例中的显式顺序或时间，或者是可以从图结构派生的顺序。这是因为所有有向无环图都具有拓扑排序，即至少有一种方法可以将顶点按顺序排列，使所有边沿着该顺序指向同一方向。
反之亦然。也就是说，在由有向无环图表示的任何应用程序中，都有一个因果结构，或者是示例中的显式顺序或时间，或者是可以从图结构派生的顺序。这是因为所有有向无环图都具有拓扑排序，即至少有一种方法可以将顶点按顺序排列，使所有边沿着该顺序指向同一方向。
===因果结构 ===
=== Causal structures 因果结构 ===
分散式版本控制版本的历史，比如 Git，通常有一个有向无环图版本的结构，每个版本都有一个顶点，一条边连接直接从其他版本派生出来的修订对。由于合并，这些通常不是树。
分散式版本控制版本的历史，比如 Git，通常有一个有向无环图版本的结构，每个版本都有一个顶点，一条边连接直接从其他版本派生出来的修订对。由于合并，这些通常不是树。
在计算几何的许多随机算法中，该算法维护一个历史 DAG，它表示一个几何结构在一系列结构变化过程中的版本历史。例如，在一个随机增量的三角形算法中，每增加一个点，三角形就被三个更小的三角形替换，或者用一对不同的三角形“翻转”操作替换成对的三角形，从而改变了三角形德劳内三角化。该算法的历史 DAG 包含每个三角形的顶点，以及每个三角形到其他两三个三角形的边。这种结构允许有效地回答点位置查询: 要在德劳内三角化中找到查询点的位置，按照历史 DAG 中的路径，在每一步移动到包含的替换三角形。在这条路径中达到的最后一个三角形必须是包含。
在计算几何的许多随机算法中，该算法维护一个历史 DAG，它表示一个几何结构在一系列结构变化过程中的版本历史。例如，在一个随机增量的三角形算法中，每增加一个点，三角形就被三个更小的三角形替换，或者用一对不同的三角形“翻转”操作替换成对的三角形，从而改变了三角形德劳内三角化。该算法的历史 DAG 包含每个三角形的顶点，以及每个三角形到其他两三个三角形的边。这种结构允许有效地回答点位置查询: 要在德劳内三角化中找到查询点的位置，按照历史 DAG 中的路径，在每一步移动到包含的替换三角形。在这条路径中达到的最后一个三角形必须是包含。
有时事件与特定的物理时间无关。假设事件对具有纯因果关系，即边表示事件之间的因果关系，我们将得到一个有向无环图。举例来说，贝叶斯网络表示多个概率事件的关联网络。顶点表示事件，后续事件的发生可能性则可以通过其在有向无环图的前驱节点的发生概率计算出来。[39]在此基础上，一个有向无环图的端正图（英语：moral graph）通过以下方法而得到：将单个顶点的所有父节点之间添加一条无向边，再将所有的有向边换成无向边。[40]
有时事件与特定的物理时间无关。假设事件对具有纯因果关系，即边表示事件之间的因果关系，我们将得到一个有向无环图。举例来说，贝叶斯网络表示多个概率事件的关联网络。顶点表示事件，后续事件的发生可能性则可以通过其在有向无环图的前驱节点的发生概率计算出来。[39]在此基础上，一个有向无环图的端正图（英语：moral graph）通过以下方法而得到：将单个顶点的所有父节点之间添加一条无向边，再将所有的有向边换成无向边。[40]
另外一种具有相似因果结构的图是影响图（英语：influence diagram）。其顶点表示决策或不确定的事件，边表示两个顶点之间的因果关系。[41]在流行病学中，这些表示因果关系的图表常常用来评估不同干预手段的效果。[42][43]
另外一种具有相似因果结构的图是影响图（英语：influence diagram）。其顶点表示决策或不确定的事件，边表示两个顶点之间的因果关系。[41]在流行病学中，这些表示因果关系的图表常常用来评估不同干预手段的效果。[42][43]
反之亦然。也就是说，在由有向无环图表示的任何应用程序中，都有一个因果结构，或者是示例中的显式顺序或时间，或者是可以从图结构派生的顺序。这是因为所有有向无环图都具有拓扑排序，即至少有一种方法可以将顶点按顺序排列，使所有边沿着该顺序指向同一方向。
反之亦然。也就是说，在由有向无环图表示的任何应用程序中，都有一个因果结构，或者是示例中的显式顺序或时间，或者是可以从图结构派生的顺序。这是因为所有有向无环图都具有拓扑排序，即至少有一种方法可以将顶点按顺序排列，使所有边沿着该顺序指向同一方向。
=== 引用图 ===
=== Citation graphs 引用图 ===
在引用图（英语：citation graph）中， 每个顶点代表单篇著作，边代表著作之间的引用关系。1965年普莱斯的文章“科学文献的网络”是使用引用图的一个经典例子。[49]在引用图中，每篇论文的引用次数（英语：Citation impact）为对应顶点的入度。这是引文分析中的一种重要的展示方式。另一个例子是法律裁判中，法官通过引用过往案例中的判决来支持他们的结论。引用图亦可以用来描绘专利，因为专利必须要提及现有技术，即已经公开的并且和本专利有关的先前专利。
在引用图（英语：citation graph）中， 每个顶点代表单篇著作，边代表著作之间的引用关系。1965年普莱斯的文章“科学文献的网络”是使用引用图的一个经典例子。[49]在引用图中，每篇论文的引用次数（英语：Citation impact）为对应顶点的入度。这是引文分析中的一种重要的展示方式。另一个例子是法律裁判中，法官通过引用过往案例中的判决来支持他们的结论。引用图亦可以用来描绘专利，因为专利必须要提及现有技术，即已经公开的并且和本专利有关的先前专利。
相较于网络科学中对一般图的研究，有向无环图的独特性质可以被用来作深层次分析。例如，传递规约可以呈现引用在不同应用领域的分布情况，这突出了不同领域中不同的引用网构造机制。[50]引用图的衍生概念还有主干道路分析（英语：Main path analysis），即对引用图中最显著的一条路径的分析。
相较于网络科学中对一般图的研究，有向无环图的独特性质可以被用来作深层次分析。例如，传递规约可以呈现引用在不同应用领域的分布情况，这突出了不同领域中不同的引用网构造机制。[50]引用图的衍生概念还有主干道路分析（英语：Main path analysis），即对引用图中最显著的一条路径的分析。
缩放。
缩放。
===Data compression 数据压缩===
===数据压缩===
有向无环图也可以用于对一系列序列的压缩中。在这里，有向无环图中的路径代表这些序列。当多个序列有共同的子序列时，子序列可以被表示为这些序列对应路径的公共边。比起直接列出所有序列，这种方法占用更少空间。例如，有向无环词图（英语：Deterministic acyclic finite state automaton）为仅含单个源（入度为0的顶点）的有向无环图，其每条边附有一个或多个字符。每条其源到汇（出度为0的节点）的路径均代表一个字符串，字符串可以是英文单词。[51]与其结构不同但功能相似的树称为trie。相比于trie，有向无环词图允许多条边指向同一个顶点，使得具有相同后缀的一些词的词头可以被相同的顶点所表示，因而更省空间。[52]
有向无环图也可以用于对一系列序列的压缩中。在这里，有向无环图中的路径代表这些序列。当多个序列有共同的子序列时，子序列可以被表示为这些序列对应路径的公共边。比起直接列出所有序列，这种方法占用更少空间。例如，有向无环词图（英语：Deterministic acyclic finite state automaton）为仅含单个源（入度为0的顶点）的有向无环图，其每条边附有一个或多个字符。每条其源到汇（出度为0的节点）的路径均代表一个字符串，字符串可以是英文单词。[51]与其结构不同但功能相似的树称为trie。相比于trie，有向无环词图允许多条边指向同一个顶点，使得具有相同后缀的一些词的词头可以被相同的顶点所表示，因而更省空间。[52]
二元决策图是基于有向无环图的一种数据结构，用于表示布尔函数[53][54]。在二元决策图中，每个非汇节点对应一个布尔变量，每个汇和边则表示0或1。要找到一个解释的真值，只要从唯一的源顶点出发，沿着该顶点代表的布尔变量的实际真值所对应的出边一直前进，到达的汇则为其真值。如同有向无环词图可以被看作是trie的一种压缩形式一样，二元决策图可以被看作是决策树的压缩形式。它通过将导向相同结果的边重新汇合到一个顶点来节省空间。[55]
二元决策图是基于有向无环图的一种数据结构，用于表示布尔函数[53][54]。在二元决策图中，每个非汇节点对应一个布尔变量，每个汇和边则表示0或1。要找到一个解释的真值，只要从唯一的源顶点出发，沿着该顶点代表的布尔变量的实际真值所对应的出边一直前进，到达的汇则为其真值。如同有向无环词图可以被看作是trie的一种压缩形式一样，二元决策图可以被看作是决策树的压缩形式。它通过将导向相同结果的边重新汇合到一个顶点来节省空间。[55]