387
个编辑
更改
跳到导航
跳到搜索
第1行：
第1行： − 此词条暂由彩云小译翻译，翻译字数共4005，未经人工整理和审校，带来阅读不便，请见谅。 − − {{short description|Directed graph with no directed cycles}} − − {{good article}} − − [[File:Tred-G.svg|thumb|Example of a directed acyclic graph.]] − − Example of a directed acyclic graph. − − 有向无环图的例子。 − − In [[mathematics]], particularly [[graph theory]], and [[computer science]], a '''directed acyclic graph''' ('''DAG''' or '''dag''' {{IPAc-en|audio=en-us-DAG.ogg|ˈ|d|æ|g}}) is a [[directed graph]] with no [[Cycle graph#Directed cycle graph|directed cycles]]. That is, it consists of [[Vertex (graph theory)|vertices]] and [[edge (graph theory)|edges]] (also called ''arcs''), with each edge directed from one vertex to another, such that following those directions will never form a closed loop. A directed graph is a DAG if and only if it can be [[topological ordering|topologically ordered]], by arranging the vertices as a linear ordering that is consistent with all edge directions. DAGs have numerous scientific and computational applications, ranging from biology (evolution, family trees, epidemiology) to sociology (citation networks) to computation (scheduling). − − In mathematics, particularly graph theory, and computer science, a directed acyclic graph (DAG or dag ) is a directed graph with no directed cycles. That is, it consists of vertices and edges (also called arcs), with each edge directed from one vertex to another, such that following those directions will never form a closed loop. A directed graph is a DAG if and only if it can be topologically ordered, by arranging the vertices as a linear ordering that is consistent with all edge directions. DAGs have numerous scientific and computational applications, ranging from biology (evolution, family trees, epidemiology) to sociology (citation networks) to computation (scheduling). − 第20行：
第4行： − + − A [[Graph (discrete mathematics)|graph]] is formed by [[vertex (graph theory)|vertices]] and by [[edge (graph theory)|edges]] connecting pairs of vertices, where the vertices can be any kind of object that is connected in pairs by edges. In the case of a [[directed graph]], each edge has an orientation, from one vertex to another vertex. A [[Path (graph theory)|path]] in a directed graph is a sequence of edges having the property that the ending vertex of each edge in the sequence is the same as the starting vertex of the next edge in the sequence; a path forms a cycle if the starting vertex of its first edge equals the ending vertex of its last edge. A directed acyclic graph is a directed graph that has no cycles.<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> − A graph is formed by vertices and by edges connecting pairs of vertices, where the vertices can be any kind of object that is connected in pairs by edges. In the case of a directed graph, each edge has an orientation, from one vertex to another vertex. A path in a directed graph is a sequence of edges having the property that the ending vertex of each edge in the sequence is the same as the starting vertex of the next edge in the sequence; a path forms a cycle if the starting vertex of its first edge equals the ending vertex of its last edge. A directed acyclic graph is a directed graph that has no cycles. − − − A vertex {{mvar|v}} of a directed graph is said to be [[Reachability|reachable]] from another vertex {{mvar|u}} when there exists a path that starts at {{mvar|u}} and ends at {{mvar|v}}. As a special case, every vertex is considered to be reachable from itself (by a path with zero edges). If a vertex can reach itself via a nontrivial path (a path with one or more edges), then that path is a cycle, so another way to define directed acyclic graphs is that they are the graphs in which no vertex can reach itself via a nontrivial path.<ref>{{citation|title=Simulation Techniques for Discrete Event Systems|volume=14|series=Cambridge Computer Science Texts|first=I.|last=Mitrani|year=1982|publisher=Cambridge University Press|isbn=9780521282826|page=27|url=https://books.google.com/books?id=CF04AAAAIAAJ&pg=PA27}}.</ref> − − A vertex of a directed graph is said to be reachable from another vertex when there exists a path that starts at and ends at . As a special case, every vertex is considered to be reachable from itself (by a path with zero edges). If a vertex can reach itself via a nontrivial path (a path with one or more edges), then that path is a cycle, so another way to define directed acyclic graphs is that they are the graphs in which no vertex can reach itself via a nontrivial path. 第40行：
第17行： − + − + − − − {{multiple image|image1=Tred-G.svg − |width1=175|image2=Tred-Gprime.svg|width2=124|caption1=A DAG {{mvar|G}}|caption2=Transitive reduction of {{mvar|G}}}} − − The [[reachability]] relationship in any directed acyclic graph can be formalized as a [[partial order]] {{math|≤}} on the vertices of the DAG. In this partial order, two vertices {{mvar|u}} and {{mvar|v}} are ordered as {{math|''u'' ≤ ''v''}} exactly when there exists a directed path from {{mvar|u}} to {{mvar|v}} in the DAG; that is, when {{mvar|v}} is reachable from {{mvar|u}}.<ref>{{citation|title=The Design and Analysis of Algorithms|series=Monographs in Computer Science|first=Dexter|last=Kozen|author-link=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> However, different DAGs may give rise to the same reachability relation and the same partial order.<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> For example, the DAG with two edges {{math|''a'' → ''b''}} and {{math|''b'' → ''c''}} has the same reachability relation as the graph with three edges {{math|''a'' → ''b''}}, {{math|''b'' → ''c''}}, and {{math|''a'' → ''c''}}. Both of these DAGS produce the same partial order, in which the vertices are ordered as {{math|''a'' ≤ ''b'' ≤ ''c''}}. − − The reachability relationship in any directed acyclic graph can be formalized as a partial order on the vertices of the DAG. In this partial order, two vertices and are ordered as exactly when there exists a directed path from to in the DAG; that is, when is reachable from . However, different DAGs may give rise to the same reachability relation and the same partial order. For example, the DAG with two edges and has the same reachability relation as the graph with three edges , , and . Both of these DAGS produce the same partial order, in which the vertices are ordered as . − [[File:Hasse diagram of powerset of 3.svg|thumb|300px|A [[Hasse diagram]] representing the partial order of set inclusion (⊆) among the subsets of a three-element set.]] − − A [[Hasse diagram representing the partial order of set inclusion (⊆) among the subsets of a three-element set.]] − − [[ Hasse 图表示三元素集合子集中集合包含(something)的偏序]] − − If {{mvar|G}} is a DAG, its [[transitive closure]] is the graph with the most edges that represents the same reachability relation. It has an edge {{math|''u'' → ''v''}} whenever {{mvar|u}} can reach {{mvar|v}}. That is, it has an edge for every related pair {{math|''u'' ≤ ''v''}} of distinct elements in the reachability relation of {{mvar|G}}, and may therefore be thought of as a direct translation of the reachability relation {{math|≤}} into graph-theoretic terms. The same method of translating partial orders into DAGs works more generally: for every finite partially ordered set {{math|(''S'', ≤)}}, the graph that has a vertex for each member of {{mvar|S}} and an edge for each pair of elements related by {{math|''u'' ≤ ''v''}} is automatically a transitively closed DAG, and has {{math|(''S'', ≤)}} as its reachability relation. In this way, every finite partially ordered set can be represented as the reachability relation of a DAG. − − If is a DAG, its transitive closure is the graph with the most edges that represents the same reachability relation. It has an edge whenever can reach . That is, it has an edge for every related pair of distinct elements in the reachability relation of , and may therefore be thought of as a direct translation of the reachability relation into graph-theoretic terms. The same method of translating partial orders into DAGs works more generally: for every finite partially ordered set , the graph that has a vertex for each member of and an edge for each pair of elements related by is automatically a transitively closed DAG, and has as its reachability relation. In this way, every finite partially ordered set can be represented as the reachability relation of a DAG. 第70行：
第30行： − The [[transitive reduction]] of a DAG {{mvar|G}} is the graph with the fewest edges that represents the same reachability relation as {{mvar|G}}. It is a subgraph of {{mvar|G}}, formed by discarding the edges {{math|''u'' → ''v''}} for which {{mvar|G}} also contains a longer path connecting the same two vertices. − − The transitive reduction of a DAG is the graph with the fewest edges that represents the same reachability relation as . It is a subgraph of , formed by discarding the edges for which also contains a longer path connecting the same two vertices. − − − Like the transitive closure, the transitive reduction is uniquely defined for DAGs. In contrast, for a directed graph that is not acyclic, there can be more than one minimal subgraph with the same reachability relation.<ref>{{citation|title=Digraphs: Theory, Algorithms and Applications|series=Springer Monographs in Mathematics|first1=Jørgen|last1=Bang-Jensen|first2=Gregory Z.|last2=Gutin|publisher=Springer|year=2008|isbn=978-1-84800-998-1|url=https://books.google.com/books?id=4UY-ucucWucC&pg=PA36|contribution=2.3 Transitive Digraphs, Transitive Closures and Reductions|pages=36–39}}.</ref> − Like the transitive closure, the transitive reduction is uniquely defined for DAGs. In contrast, for a directed graph that is not acyclic, there can be more than one minimal subgraph with the same reachability relation. − If a DAG {{mvar|G}} has a reachability relation described by the partial order {{math|≤}}, then the transitive reduction of {{mvar|G}} is a subgraph of {{mvar|G}} that has an edge {{math|''u'' → ''v''}} for every pair in the [[covering relation]] of {{math|≤}}. Transitive reductions are useful in visualizing the partial orders they represent, because they have fewer edges than other graphs representing the same orders and therefore lead to simpler [[graph drawing]]s. A [[Hasse diagram]] of a partial order is a drawing of the transitive reduction in which the orientation of each edge is shown by placing the starting vertex of the edge in a lower position than its ending vertex.<ref>{{citation|title=Graphs, Networks and Algorithms|volume=5|series=Algorithms and Computation in Mathematics|first=Dieter|last=Jungnickel|publisher=Springer|year=2012|isbn=978-3-642-32278-5|pages=92–93|url=https://books.google.com/books?id=PrXxFHmchwcC&pg=PA92}}.</ref> − If a DAG has a reachability relation described by the partial order , then the transitive reduction of is a subgraph of that has an edge for every pair in the covering relation of . Transitive reductions are useful in visualizing the partial orders they represent, because they have fewer edges than other graphs representing the same orders and therefore lead to simpler graph drawings. A Hasse diagram of a partial order is a drawing of the transitive reduction in which the orientation of each edge is shown by placing the starting vertex of the edge in a lower position than its ending vertex. − + − − {{multiple image|image1=Topological Ordering.svg|caption1=A [[Topological sorting|topological ordering]] of a directed acyclic graph: every [[Edge (graph theory)|edge]] goes from earlier in the ordering (upper left) to later in the ordering (lower right). A directed graph is acyclic if and only if it has a topological ordering.|image2=Transitive Closure.svg|caption2=Adding the red edges to the blue directed acyclic graph produces another DAG, the [[transitive closure]] of the blue graph. For each red or blue edge {{mvar|uv}}, {{mvar|v}} is [[Reachability|reachable]] from {{mvar|u}}: there exists a blue path starting at {{mvar|u}} and ending at {{mvar|v}}.}} − − − − A [[topological ordering]] of a directed graph is an ordering of its vertices into a sequence, such that for every edge the start vertex of the edge occurs earlier in the sequence than the ending vertex of the edge. A graph that has a topological ordering cannot have any cycles, because the edge into the earliest vertex of a cycle would have to be oriented the wrong way. Therefore, every graph with a topological ordering is acyclic. Conversely, every directed acyclic graph has at least one topological ordering. The existence of a topological ordering can therefore be used as an equivalent definition of a directed acyclic graphs: they are exactly the graphs that have topological orderings.<ref name="bang"/> − − A topological ordering of a directed graph is an ordering of its vertices into a sequence, such that for every edge the start vertex of the edge occurs earlier in the sequence than the ending vertex of the edge. A graph that has a topological ordering cannot have any cycles, because the edge into the earliest vertex of a cycle would have to be oriented the wrong way. Therefore, every graph with a topological ordering is acyclic. Conversely, every directed acyclic graph has at least one topological ordering. The existence of a topological ordering can therefore be used as an equivalent definition of a directed acyclic graphs: they are exactly the graphs that have topological orderings. − − In general, this ordering is not unique; a DAG has a unique topological ordering if and only if it has a directed path containing all the vertices, in which case the ordering is the same as the order in which the vertices appear in the path.<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> − − The family of topological orderings of a DAG is the same as the family of linear extensions of the reachability relation for the DAG, so any two graphs representing the same partial order have the same set of topological orders.
无编辑摘要
在数学，特别是<font color="#ff8000">图论</font>和<font color="#ff8000">计算机科学</font>中，有向无环图<font color="#ff8000">DAG 或 dag</font>是一个没有定向循环的有向图。也就是说，它由<font color="#ff8000">顶点Vertex</font>和<font color="#ff8000">边Edge</font>(也称为弧)组成，每条边都从一个顶点指向另一个顶点，沿着这些顶点的方向 不会形成一个闭合的<font color="#ff8000">环Loop</font>。有向图是一个有向无环图当且仅当它可以通过将顶点按照与所有边方向一致的线性顺序排列构成<font color="#ff8000">拓扑排序Topologically ordered</font>。有向无环图有许多科学的和计算的应用，从生物学(进化论，家谱，流行病学)到社会学(引文网络)到计算(调度)。
在数学，特别是<font color="#ff8000">图论</font>和<font color="#ff8000">计算机科学</font>中，有向无环图<font color="#ff8000">DAG 或 dag</font>是一个没有定向循环的有向图。也就是说，它由<font color="#ff8000">顶点Vertex</font>和<font color="#ff8000">边Edge</font>(也称为弧)组成，每条边都从一个顶点指向另一个顶点，沿着这些顶点的方向 不会形成一个闭合的<font color="#ff8000">环Loop</font>。有向图是一个有向无环图当且仅当它可以通过将顶点按照与所有边方向一致的线性顺序排列构成<font color="#ff8000">拓扑排序Topologically ordered</font>。有向无环图有许多科学的和计算的应用，从生物学(进化论，家谱，流行病学)到社会学(引文网络)到计算(调度)。
==Definitions==
==定义==
图是由顶点和连接顶点对的边组成的，顶点可以是任何一种由边成对连接的对象。在有向图中，每条边都有一个方向，从一个顶点到另一个顶点。有向图中的<font color="#ff8000">路径Path</font>是一个边序列，序列中每条边的结束顶点是序列中下一条边的起始顶点; 如果一条路的第一条边的起始顶点与它的最后一条边的结束顶点相同，那么它就形成了一个环。有向无环图是一个没有环的有向图[1][2][3]。
图是由顶点和连接顶点对的边组成的，顶点可以是任何一种由边成对连接的对象。在有向图中，每条边都有一个方向，从一个顶点到另一个顶点。有向图中的<font color="#ff8000">路径Path</font>是一个边序列，序列中每条边的结束顶点是序列中下一条边的起始顶点; 如果一条路的第一条边的起始顶点与它的最后一条边的结束顶点相同，那么它就形成了一个环。有向无环图是一个没有环的有向图[1][2][3]。
当存在一条从顶点u到顶点v的路径时，顶点v被称作是从顶点u<font color="#ff8000">可达的Reachability</font>。每个顶点都是从自身可达的（通过一条没有边的路径）。如果一个顶点可以从一条<font color="#32cd32"> 非平凡</font>路径（一条由一个或更多边组成的路径）到达自身，那么这条路径就是一个环。因此，有向无环图也可以被定义为没有顶点可以通过非平凡路径到达自身的图。[4]
当存在一条从顶点u到顶点v的路径时，顶点v被称作是从顶点u<font color="#ff8000">可达的Reachability</font>。每个顶点都是从自身可达的（通过一条没有边的路径）。如果一个顶点可以从一条<font color="#32cd32"> 非平凡</font>路径（一条由一个或更多边组成的路径）到达自身，那么这条路径就是一个环。因此，有向无环图也可以被定义为没有顶点可以通过非平凡路径到达自身的图。[4]
== Mathematical properties 数学性质 ==
== 数学性质 ==
=== Reachability, transitive closure, and transitive reduction 可达性，传递闭包和传递归约===
=== 可达性，传递闭包和传递归约===
有向无环图的可达性可以用其顶点的<font color="#ff8000"> 偏序关系</font>≤来表示。在偏序关系中，如果存在一条路径从顶点u指向顶点v，它们的偏序关系可被写作u ≤ v。也就是，从节点u是可达节点v。[5] 不同的有向无环图可以有着相同的可达关系和偏序关系[6]。例如，有两条边a → b，b → c的有向无环图，和有三条边的a → b, b → c，a → c的有向无环图有着相同的偏序关系a ≤ b ≤ c。
有向无环图的可达性可以用其顶点的<font color="#ff8000"> 偏序关系</font>≤来表示。在偏序关系中，如果存在一条路径从顶点u指向顶点v，它们的偏序关系可被写作u ≤ v。也就是，从节点u是可达节点v。[5] 不同的有向无环图可以有着相同的可达关系和偏序关系[6]。例如，有两条边a → b，b → c的有向无环图，和有三条边的a → b, b → c，a → c的有向无环图有着相同的偏序关系a ≤ b ≤ c。
对于一个有向无环图G，它的传递闭包等同于一个在保持与其相同可达性的情况下，边数最多的图。在这个图中，当u可达v的时候，边u → v必定存在。换句话说，每个G中的非相同元素偏序关系对u ≤ v都在这个图中有一条边。这可以被视作用图来可视化图G的可达性关系。
对于一个有向无环图G，它的传递闭包等同于一个在保持与其相同可达性的情况下，边数最多的图。在这个图中，当u可达v的时候，边u → v必定存在。换句话说，每个G中的非相同元素偏序关系对u ≤ v都在这个图中有一条边。这可以被视作用图来可视化图G的可达性关系。
有向无环图G的传递规约为和其有着相同可达性，边数最少的图。它是G的一个子图。构造方法为当G有着一条更长的路径连接顶点u和v的时候，消去边u → v。 传递约简和传递闭包都是有向无环图的特有概念。相反的，对于有向有环图，可以存在多个与原图有着相同可达性的最简子图。[7]
有向无环图G的传递规约为和其有着相同可达性，边数最少的图。它是G的一个子图。构造方法为当G有着一条更长的路径连接顶点u和v的时候，消去边u → v。 传递约简和传递闭包都是有向无环图的特有概念。相反的，对于有向有环图，可以存在多个与原图有着相同可达性的最简子图。[7]
对于有向无环图G和表达其可达性的偏序关系≤，它的传递规约也可以看作包含G的覆盖关系covering relation中每一条边的G的子图。传递规约在图示有向无环图的偏序关系时十分有用，因为它们比其他具有相同偏序关系的图的边数要少，这简化了绘图。偏序关系的哈斯图由将传递规约中的每条边的起点绘制在其终点的下方而得到。[9]
对于有向无环图G和表达其可达性的偏序关系≤，它的传递规约也可以看作包含G的覆盖关系covering relation中每一条边的G的子图。传递规约在图示有向无环图的偏序关系时十分有用，因为它们比其他具有相同偏序关系的图的边数要少，这简化了绘图。偏序关系的哈斯图由将传递规约中的每条边的起点绘制在其终点的下方而得到。[9]
=== Topological ordering 拓扑排序===
=== 拓扑排序===
有向无环图的拓扑排序为所有边的起点都出现在其终点之前的排序。能构成拓扑排序的图一定没有环，因为环中的一条边必定从排序较后的顶点指向比其排序更前的顶点。基于此，拓扑排序可以被用来定义有向无环图：当且仅当一个有向图有拓扑排序，它是有向无环图。一般情况下，拓扑排序并非唯一。有向无环图仅仅在存在一条路径可以包含其所有顶点的情况下，有唯一的拓扑排序方式，这时，拓扑排序与顶点在这条路径中出现的顺序相同。[9]
有向无环图的拓扑排序为所有边的起点都出现在其终点之前的排序。能构成拓扑排序的图一定没有环，因为环中的一条边必定从排序较后的顶点指向比其排序更前的顶点。基于此，拓扑排序可以被用来定义有向无环图：当且仅当一个有向图有拓扑排序，它是有向无环图。一般情况下，拓扑排序并非唯一。有向无环图仅仅在存在一条路径可以包含其所有顶点的情况下，有唯一的拓扑排序方式，这时，拓扑排序与顶点在这条路径中出现的顺序相同。[9]
有向无环图的拓扑序族与有向无环图的可达关系的线性扩张族相同，因此任意两个表示相同偏序的图具有相同的拓扑序集。
有向无环图的拓扑序族与有向无环图的可达关系的线性扩张族相同，因此任意两个表示相同偏序的图具有相同的拓扑序集。