387
个编辑
更改
跳到导航
跳到搜索
第224行：
第224行： − − == Computational problems == − − − − − − === Topological sorting and recognition === − − {{Main|Topological sorting}} − − [[Topological sorting]] is the algorithmic problem of finding a topological ordering of a given DAG. It can be solved in [[linear time]].<ref name="clrs">{{Introduction to Algorithms|edition=2|mode=cs2}} Section 22.4, Topological sort, pp. 549–552.</ref> Kahn's algorithm for topological sorting builds the vertex ordering directly. It maintains a list of vertices that have no incoming edges from other vertices that have not already been included in the partially constructed topological ordering; initially this list consists of the vertices with no incoming edges at all. Then, it repeatedly adds one vertex from this list to the end of the partially constructed topological ordering, and checks whether its neighbors should be added to the list. The algorithm terminates when all vertices have been processed in this way.<ref name="j50" /> Alternatively, a topological ordering may be constructed by reversing a [[postorder]] numbering of a [[depth-first search]] graph traversal.<ref name="clrs" /> − − − − It is also possible to check whether a given directed graph is a DAG in linear time, either by attempting to find a topological ordering and then testing for each edge whether the resulting ordering is valid<ref>For [[depth-first search]] based topological sorting algorithm, this validity check can be interleaved with the topological sorting algorithm itself; see e.g. {{citation|title=The Algorithm Design Manual|first=Steven S.|last=Skiena|publisher=Springer|year=2009|isbn=978-1-84800-070-4|pages=179–181|url=https://books.google.com/books?id=7XUSn0IKQEgC&pg=PA179}}.</ref> or alternatively, for some topological sorting algorithms, by verifying that the algorithm successfully orders all the vertices without meeting an error condition.<ref name="j50">{{harvtxt|Jungnickel|2012}}, pp. 50–51.</ref> − − Directed acyclic graphs representations of partial orderings have many applications in scheduling for systems of tasks with ordering constraints. − − 偏序的有向无圈图表示在有序约束的任务系统的调度中有许多应用。 − − − − 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. − − 这种类型的一类重要问题涉及需要更新的对象集合，例如电子表格中某个单元格更改后的单元格，或者计算机软件中某个源代码更改后的目标文件。 − − === Construction from cyclic graphs === − − 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. − − 在此上下文中，依赖关系图是一个图，其中每个要更新的对象都有一个顶点，并且每当其中一个对象需要比另一个更早更新时，就有一条连接两个对象的边。这个图中的循环称为循环依赖，通常不允许这样做，因为没有办法始终如一地安排循环中涉及的任务。 − − Any undirected graph may be made into a DAG by choosing a [[total order]] for its vertices and directing every edge from the earlier endpoint in the order to the later endpoint. The resulting [[Orientation (graph theory)|orientation]] of the edges is called an [[acyclic orientation]]. Different total orders may lead to the same acyclic orientation, so an {{mvar|n}}-vertex graph can have fewer than {{math|''n''!}} acyclic orientations. The number of acyclic orientations is equal to {{math|{{!}}''χ''(−1){{!}}}}, where {{mvar|χ}} is the [[chromatic polynomial]] of the given graph.<ref>{{citation|first=Richard P.|last=Stanley|author-link=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> − − Dependency graphs without circular dependencies form DAGs. − − 无循环依赖关系的依赖图形成 DAGs。 − − − − [[File:Graph Condensation.svg|thumb|upright=1.5|The yellow directed acyclic graph is the [[Condensation (graph theory)|condensation]] of the blue directed graph. It is formed by [[Edge contraction|contracting]] each [[strongly connected component]] of the blue graph into a single yellow vertex.]] − − 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. Similar problems of task ordering arise in makefiles for program compilation − − 例如，当电子表格的一个单元格发生更改时，必须重新计算直接或间接依赖于更改单元格的其他单元格的值。对于此问题，计划中的任务是对电子表格各单元格的值重新计算。当一个单元格中的表达式使用另一个单元格中的值时，就会出现依赖性。在这种情况下，必须比使用该值的表达式更早地重新计算使用的值。通过拓扑排序依赖关系图，并使用这个拓扑有序表来安排单元格的更新，可以使整个电子表格只需要对每个单元格进行一次计算就可以更新。类似的任务排序问题也出现在程序编译的 makefile 中 − − Any directed graph may be made into a DAG by removing a [[feedback vertex set]] or a [[feedback arc set]], a set of vertices or edges (respectively) that touches all cycles. However, the smallest such set is [[NP-hard]] to find.<ref>{{Garey-Johnson}}, Problems GT7 and GT8, pp. 191–192.</ref> An arbitrary directed graph may also be transformed into a DAG, called its [[condensation (graph theory)|condensation]], by [[Edge contraction|contracting]] each of its [[strongly connected component]]s into a single supervertex.<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> When the graph is already acyclic, its smallest feedback vertex sets and feedback arc sets are [[empty set|empty]], and its condensation is the graph itself. − − − − 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. − − 有五个里程碑(标记为10-50)和六个任务(标记为 a-f)的项目的 PERT 图表。有两条关键路径，ADF 和 BC。 − − === Transitive closure and transitive reduction === − − 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 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 in this DAG represents the 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. − − 计划评审技术(program evaluation and review technique，PERT)使用了一种略有不同的基于 DAGs 的进度约束形式，这种方法是 DAGs 的首批应用之一，用于管理大型人类项目。在这种方法中，DAG 的顶点代表项目的里程碑，而不是要执行的具体任务。相反，一个任务或活动由一个有向无环图的边缘表示，连接两个标志任务开始和完成的里程碑。每个这样的边都标注了一个估计值，表示一组工作人员执行该任务所需的时间。DAG 中最长的路径代表项目的关键路径，它控制项目的总时间。单个里程碑可以根据在其顶点结束的最长路径的长度进行调度。 − − The transitive closure of a given DAG, with {{mvar|n}} vertices and {{mvar|m}} edges, may be constructed in time {{math|''O''(''mn'')}} by using either [[breadth-first search]] or [[depth-first search]] to test reachability from each vertex.<ref>{{harvtxt|Skiena|2009}}, p. 495.</ref> Alternatively, it can be solved in time {{math|''O''(''n''<sup>''ω''</sup>)}} where {{math|''ω'' < 2.373}} is the [[Computational complexity of matrix multiplication#Matrix multiplication exponent|exponent for matrix multiplication algorithms]]; this is a theoretical improvement over the {{math|''O''(''mn'')}} bound for [[dense graph]]s.<ref>{{harvtxt|Skiena|2009}}, p. 496.</ref> − − − − In all of these transitive closure algorithms, it is possible to distinguish pairs of vertices that are reachable by at least one path of length two or more from pairs that can only be connected by a length-one path. The transitive reduction consists of the edges that form length-one paths that are the only paths connecting their endpoints. Therefore, the transitive reduction can be constructed in the same asymptotic time bounds as the transitive closure.<ref>{{harvtxt|Bang-Jensen|Gutin|2008}}, p. 38.</ref> − − 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. − − 有向无环图可以用来表示处理元素的网络。在这种表示法中，数据通过传入边进入处理元素，通过传出边离开元素。 − − − − === Closure problem === − − For instance, in electronic circuit design, static combinational logic blocks can be represented as an acyclic system of logic gates that computes a function of an input, where the input and output of the function are represented as individual bits. 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. 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. − − 例如，在电子电路设计中，静态组合逻辑电路块可以表示为一个逻辑门的非循环系统，计算一个输入函数，其中的输入和输出被表示为单独的位。一般来说，这些块的输出不能用作输入，除非它被保持其非循环属性的寄存器或状态元素捕获。纸上或数据库中的电子电路原理图是一种有向无环图的形式，使用实例或组件形成对较低级别组件的有向引用。电子电路本身不一定是无环或有向的。 − − {{Main|Closure problem}} − − The [[closure problem]] takes as input a vertex-weighted directed acyclic graph and seeks the minimum (or maximum) weight of a closure – a set of vertices ''C'', such that no edges leave ''C''. The problem may be formulated for directed graphs without the assumption of acyclicity, but with no greater generality, because in this case it is equivalent to the same problem on the condensation of the graph. It may be solved in polynomial time using a reduction to the [[maximum flow problem]].<ref>{{citation − − Dataflow programming languages describe systems of operations on data streams, 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. − − 数据流编程语言描述了对数据流的操作系统，以及某些操作的输出和其他操作的输入之间的连接。这些语言可以方便地描述重复的数据处理任务，在这些任务中，对许多数据项应用相同的无环连接的操作集合。它们可以作为一个并行算法执行，其中每个操作在另一组输入可用时由一个并行进程执行。 − − | last = Picard | first = Jean-Claude − − | doi = 10.1287/mnsc.22.11.1268 − − In compilers, 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. 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. − − 在编译器中，直线代码(即没有循环或条件分支的语句序列)可以由 DAG 表示，DAG 描述代码中执行的每个算术运算的输入和输出。此表示形式允许编译器有效地执行公共子表达式消除。在更高层次的代码组织中，非循环依赖原则指出，大型软件系统的模块或组件之间的依赖应该形成一个有向无环图。 − − | issue = 11 − − | journal = [[Management Science (journal)|Management Science]] − − Feedforward neural networks are another example. − − 前馈神经网络是另一个例子。 − − | mr = 0403596 − − | pages = 1268–1272 − − | title = Maximal closure of a graph and applications to combinatorial problems − − | volume = 22 − − 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 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 loops. An example of this type of directed acyclic graph are those encountered in the causal set approach to quantum gravity though in this case the graphs considered are 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. − − 顶点表示在一定时间内发生的事件，并且边始终是从边的早期时间顶点到后期时间顶点的点的图，必然是有向的和无环的。没有循环是因为当你沿着图中的任何一条路径走时，与一个顶点相关的时间总是增加，所以你永远不能返回到路径上的一个顶点。这反映了我们的自然直觉，因果关系意味着事件只能影响未来，它们从不影响过去，因此我们没有因果循环。这类有向无环图的一个例子是在量子引力的因果集方法中遇到的，尽管在这种情况下所考虑的图是传递完全的。在版本历史示例中，软件的每个版本都与一个唯一的时间相关联，通常是保存、提交或发布版本的时间。对于引用图，这些文献只能发表一次，并且只能引用较早的文献。 − − | year = 1976}}.</ref> − − − − Sometimes events are not associated with a specific physical time. Provided that pairs of events have a purely causal relationship, that is edges represent causal relations between the events, we will have a directed acyclic graph. 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. 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. 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. In epidemiology, for instance, these diagrams are often used to estimate the expected value of different choices for intervention. − − 有时，事件与特定的物理时间无关。如果成对的事件具有纯粹的因果关系，即边缘代表事件之间的因果关系，那么我们就有了一个有向无环图。例如，一个贝氏网路代表一个概率事件系统作为一个有向无环图中的顶点，在这个顶点中，一个事件的可能性可以通过它在 DAG 中的前身的可能性来计算。在这种情况下，有向无环图是在同一顶点的所有父母之间加上一条(无向)边(有时称为结合) ，然后用无向边代替所有有向边而产生的无向图。另一种具有类似因果结构的图类型是影响图，其顶点表示要作出的决定或未知信息，其边表示从一个顶点到另一个顶点的因果影响。例如，在流行病学中，这些图表通常用于估计不同干预选择的期望值。 − − === Path algorithms === − − Some algorithms become simpler when used on DAGs instead of general graphs, based on the principle of topological ordering. For example, it is possible to find [[shortest path]]s and [[longest path problem|longest paths]] from a given starting vertex in DAGs in linear time by [[Topological sorting#Application to shortest path finding|processing the vertices in a topological order]], and calculating the path length for each vertex to be the minimum or maximum length obtained via any of its incoming edges.<ref>Cormen et al. 2001, Section 24.2, Single-source shortest paths in directed acyclic graphs, pp. 592–595.</ref> In contrast, for arbitrary graphs the shortest path may require slower algorithms such as [[Dijkstra's algorithm]] or the [[Bellman–Ford algorithm]],<ref>Cormen et al. 2001, Sections 24.1, The Bellman–Ford algorithm, pp. 588–592, and 24.3, Dijkstra's algorithm, pp. 595–601.</ref> and longest paths in arbitrary graphs are [[NP-hard]] to find.<ref>Cormen et al. 2001, p. 966.</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. − − 反之亦然。也就是说，在任何用有向无环图表示的应用程序中，都存在一个因果结构，要么是例子中显式的顺序或时间，要么是可以从图结构中派生出来的顺序。这是因为所有有向无圈图都有一个拓扑序，即。至少有一种方法可以将顶点按顺序排列，使所有边沿着这个顺序指向同一个方向。
→Computational problems
的贝尔曼-福特算法等。[28]最长路径则是一个NP困难问题。[29]
的贝尔曼-福特算法等。[28]最长路径则是一个NP困难问题。[29]
== Applications ==
== Applications ==