有向无环图的这些“后代”子图有一个术语吗？

Question

考虑有向无环图 $G$ 带顶点集 $V$. 。选择一个顶点 $v$, ， 然后让 $H$ 是包含的子图 $v$ 以及所有其他顶点 $G$ 可以从以下位置到达 $v$ （以及相关的有向边）。

（换句话说，如果我们选择 $v \in V$, ，那么我们感兴趣的是由以下组成的子集 $v$ 及其所有后代）。

对于这个特定的顶点子集（或子图）是否有一个可接受的术语？这似乎是一个相当基本的概念，所以我希望找到一个常用的短语，但到目前为止我的搜索结果是空的。感谢您的任何答案或线索！

Answer 1

有点儿。但我们将使用通常的计算机科学方式来描述这一点，使用以下语言： 二元关系.

您可能已经熟悉二元关系，例如相等 $=$, 小于或等于 $\le$, 子集 $\子集$, ， 等等。一般来说，二元关系 $R$ 超过一组 $X$ 是一个子集 $R \subseteq X imes X$. 。如果 $(x,y) \in R$, ，我们将其表示为 $xRy$.

如果 $\forall x \in X, xRx$, ， 然后 $R$ 是 反射性的. 。关系 $=$ 和 $\le$ 是反射性的，但是 $\lt$ 不是。

如果 $\forall x, y, z \in X, xRy\,\wedge\,yRz ightarrow xRz$, ， 然后 $R$ 是 及物的. 。许多关系是传递的，包括上面给出的所有关系。如果 $x \le y$ 和 $y \le z$, ， 然后 $x \le z$.

给定一个关系 $R$, ， 这 自反传递闭包 的 $R$, ，表示为 $R^*$, 是最小关系 $R^*$ 这样 $R \subseteq R^*$, ， 和 $R^*$ 是自反和及物的。

将图解释为二元关系（因为边对您来说似乎并不重要，您只对顶点集感兴趣），这正是您想要的： $xR^*y$ 当且仅当 $y$ 是（按照你的意思）的“后代” $x$.

在看文献时，你还需要知道一个符号：这 传递闭包 的 $R$, ，表示为 $R^+$, 是最小关系 $R^+$ 这样 $R \subseteq R^+$, ， 和 $R^+$ 是传递性的。用于计算传递闭包和自反传递闭包的算法是相关的，因为它们仅在“对角线”条目上有所不同： $R^+ \cup \left\{ (x,x)\,|\,x \in X ight\} = R^*$.

有多种标准算法可用于计算关系的 RTC。如果关系是稠密的，即可以将其表示为位矩阵，则 Floyd-Warshall 算法 是最快的实用算法之一；它的运行时间是 $\θ(|V|^3)$ 理论上，但考虑到内部循环是一堆位向量操作，因此在实际硬件上内部循环非常快。

对于稀疏关系，请参见 Esko Nuutila 的论文, ，其中包含一个非常好的调查以及一些更新的算法。