DAG

在图论中，如果一个有向图从任意顶点出发无法经过若干条边回到该点，则这个图是一个有向无环图（英语：Directed Acyclic Graph，缩写：DAG）。
因为有向无环图中从一个点到另一个点有可能存在两种路线，因此有向无环图未必能转化成树，但任何有向树均为有向无环图。

== 定义 ==
图由顶点和连接这些顶点的边所构成。每条边都带有从一个顶点指向另一个顶点的方向的图为有向图。有向图中的道路为一系列的边，系列中每条边的终点都是下一条边的起点。如果一条路径的起点是这条路径的终点，那么这条路径就是一个环。有向无环图即为没有环出现的有向图。

当存在一条从顶点u到顶点v的路径时，顶点v被称作是从顶点u可达的。每个顶点都是从自身可达的（通过一条没有边的路径）。如果一个顶点可以从一个非平凡路径（一条由一个或更多边组成的路径）到达自身，那么这条路径就是一个环。因此，有向无环图也可以被定义为没有顶点可以通过非平凡路径到达自身的图。

== 数学性质 ==

=== 可达性，传递闭包和传递归约 ===
有向无环图的可达性可以用其顶点的偏序关系≤来表示。在偏序关系中，如果存在一条路径从顶点u指向顶点v，它们的偏序关系可被写作u ≤ v。这也被称作v是从u可达的。不同的有向无环图可以有着相同的可达关系和偏序关系。例如，有两条边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。
传递约简和传递闭包都是有向无环图的特有概念。相反的，对于有向有环图，可以存在多个与原图有着相同可达性的最简子图。

对于有向无环图G和表达其可达性的偏序关系≤，它的传递规约也可以看作包含G的覆盖关系中每一条边的G的子图。传递规约在图示有向无环图的偏序关系时十分有用，因为它们比其他具有相同偏序关系的图的边数要少，这简化了绘图。偏序关系的哈斯图由将传递规约中的每条边的起点绘制在其终点的下方而得到。

=== 拓扑排序 ===
有向无环图的拓扑排序为所有边的起点都出现在其终点之前的排序。能构成拓扑排序的图一定没有环，因为环中的一条边必定从排序较后的顶点指向比其排序更前的顶点。基于此，拓扑排序可以被用来定义有向无环图：当且仅当一个有向图有拓扑排序，它是有向无环图。一般情况下，拓扑排序并非唯一。有向无环图仅仅在存在一条路径可以包含其所有顶点的情况下…