有向无环图术语

有向无环图（DAG）由一些称为“节点”的点和连接它们的单向箭头组成，箭头称为“边”；沿着箭头走，你永远无法回到起点，也就是说，图中没有环。你可以把它想成一棵家族树：父母指向孩子，但谁也不可能成为自己的祖父母。这种结构非常适合表示先后顺序很重要的情况，比如项目中任务的前置条件，或科学中的因果链。节点表示事物或事件，边表示关系或依赖；由于没有环，总能找到至少一种有效顺序，把所有节点从头到尾排好。 试试这样：规划下一个项目时，画出哪些任务依赖其他任务，你画的就是一张有向无环图。

有向无环图术语让你能准确描述这样一种结构：事物之间存在有方向的连接，但不会形成环。节点也叫顶点，是图的基本组成部分，可以表示任务、变量、事件，或任何你关注的实体。边也叫弧，是节点之间有方向的连接，总是从一个起点指向一个终点。如果你能沿着边从一个节点走到另一个节点，就找到了一条路径；路径的起点节点称为终点节点的“祖先”，终点节点则称为起点节点的“后代”。

这些术语的作用在于，它们能表达先后关系和因果关系。在项目管理中，如果任务 A 必须完成后任务 B 才能开始，就用一条从 A 指向 B 的边来表示。在因果推断中，从 X 指向 Y 的箭头表示 X 会影响 Y。不能有环这一规则很关键：它意味着总能找到至少一种有效的拓扑序，也就是把所有节点排成一行，让每条边都指向排在后面的节点。这也是构建系统、数据流水线和调度器依赖有向无环图的原因：它们保证依赖关系可以得到解决，不会卡在循环依赖中。

有向无环图还有几个专门术语。源节点没有入边，也就是没有边指向它，因此很适合作为起点。汇节点没有出边，也就是没有边从它指向别处，因此代表一个终点。传递闭包会把所有间接连接都补成直接的边：如果 A 指向 B，B 又指向 C，传递闭包就会加上一条从 A 指向 C 的边。传递约简则反过来，移除冗余的边，只保留必要的关系。有了这些术语，你就能完整地描述、分析和调整计算机科学、数据工程、因果推理等领域中的依赖结构。

有向无环图术语源于离散数学中的图论，并在计算机科学文献中得到了形式化定义。Bang-Jensen 和 Gutin（2008）全面定义了有向图的相关概念，区分了顶点（节点）和弧（有向边），并确立了有向无环图中可达性、祖先和后代的形式化性质 [1]。Cormen 等人（2022）在经典算法教材中，将拓扑序定义为顶点的一种线性排列，其中每条有向边都从排在前面的顶点指向排在后面的顶点，并证明了一个图无环，当且仅当它存在拓扑序 [2]。

关键术语的相关研究：

• Pearl（2009）：对因果有向无环图进行了形式化定义，其中节点表示随机变量，边表示直接的因果影响，并将祖先与后代关系确立为因果推断算法的基础 [3]。
• Bang-Jensen 和 Gutin（2008）：将有向无环图的传递闭包定义为这样一个图：只要从 u 能到达 v，图中就包含一条从 u 指向 v 的边；传递约简则是保留全部可达关系的最小子图 [1]。
• Cormen 等人（2022）：说明了有向无环图的拓扑排序可在线性时间内完成，因此，基于有向无环图的调度和依赖解析在计算上很高效 [2]。

有向无环图为表示偏序提供了数学基础。偏序是一种满足自反性、反对称性和传递性的关系：自反性指每个元素都与自身满足该关系；反对称性指两个元素若相互满足该关系，它们就必须是同一个元素；传递性指若第一个元素与第二个元素、第二个元素与第三个元素满足该关系，那么第一个元素与第三个元素也满足该关系。每个有限偏序集都对应一个有向无环图，而有向无环图的可达关系定义了其顶点上的偏序。

在某些领域，环本身就是基本特征，而不是需要避免的问题，这时有向无环图术语就有局限。在反馈系统、循环神经网络和许多生物过程中，循环关系必不可少。基于有向无环图的因果模型还假设关系是静态的，因此可能难以处理随时间变化的因果关系或双向因果关系。当这些术语用于边表示相关性而非直接因果关系的概率图模型时，含义可能变得模糊。此外，拓扑序并不唯一：大多数有向无环图都有多种有效排列，这可能让你难以判断在具体应用中哪种排列才是“正确”的。