更改

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).

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).

在数学，特别是<font color="#ff8000">图论</font>和<font color="#ff8000">计算机科学</font>中，有向无环图图(DAG 或 dag)是一个没有定向循环的有向图。也就是说，它由<font color="#ff8000">节点</font>（Vertex）和<font color="#ff8000">边</font>(也称为弧)（Edge）组成，每条边都从一个节点指向另一个节点，沿着这些节点的方向 不会形成一个闭合的<font color="#ff8000">环</font>（loop）。有向图是一个有向无环图当且仅当它可以通过将节点按照与所有边方向一致的线性顺序排列构成<font color="#ff8000">拓扑排序</font>（topologically ordered）。DAGs 有许多科学的和计算的应用，从生物学(进化论，家谱，流行病学)到社会学(引文网络)到计算(调度)。

在数学，特别是<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>。有向无环图有许多科学的和计算的应用，从生物学(进化论，家谱，流行病学)到社会学(引文网络)到计算(调度)。

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 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.

图是由顶点和连接顶点对的边组成的，顶点可以是任何一种由边成对连接的对象。在有向图的情况下，每条边都有一个方向，从一个顶点到另一个顶点。有向图中的路是一个边序列，它具有序列中每条边的结束顶点与序列中下一条边的起始顶点相同的性质; 如果一条路的第一条边的起始顶点与它的最后一条边的结束顶点相等，那么它就形成了一个圈。有向无环图是一个没有圈的有向图。

图是由顶点和连接顶点对的边组成的，顶点可以是任何一种由边成对连接的对象。在有向图中，每条边都有一个方向，从一个顶点到另一个顶点。有向图中的<font color="#ff8000">路径Path</font>是一个边序列，序列中每条边的结束顶点是序列中下一条边的起始顶点; 如果一条路的第一条边的起始顶点与它的最后一条边的结束顶点相同，那么它就形成了一个环。有向无环图是一个没有环的有向图[1][2][3]。

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.

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.

 

 

== Mathematical properties ==

== Mathematical properties ==

 

=== Reachability, transitive closure, and transitive reduction ===

=== Reachability, transitive closure, and transitive reduction ===

 

{{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}}}}

{{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]] {{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 .

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 .

任何有向无环图中的可达关系都可以形式化为 DAG 顶点上的一个偏序。在这个部分顺序中，两个顶点的顺序与有向无环图中存在从到的有向路径时的顺序完全一致; 也就是说，当从。然而，不同的 DAGs 可能产生相同的可达关系和相同的偏序。例如，有向无环图具有两条边，并且与具有三条边、和的图具有相同的可达性关系。这两种 DAGS 产生相同的偏序，其中顶点的顺序为。

 

 

在这个部分顺序中，两个顶点的顺序与有向无环图中存在从到的有向路径时的顺序完全一致; 也就是说，当从。然而，不同的 DAGs 可能产生相同的可达关系和相同的偏序。例如，有向无环图具有两条边，并且与具有三条边、和的图具有相同的可达性关系。这两种 DAGS 产生相同的偏序，其中顶点的顺序为。