将有向图编码为数字

Question

假设我有一个有向图，具有单根且没有循环。我想在每个节点上添加一个具有以下属性的类型（例如作为具有某些自定义排序的整数）：

if Node1.type <= Node2.type then there exists a path from Node1 to Node2

请注意，拓扑排序实际上满足反转性质：

if there exists a path from Node1 to Node2 then Node1.type <= Node2.type

所以不能在这里使用。

现在请注意，这里不能使用具有自然排序的整数，因为每 2 个整数都可以进行比较，即整数的排序是线性的，而树不必是线性的。

这是一个例子。假设该图有 4 个节点A, B, C, D和 4 个箭头：

A->B, A->C, B->D, C->D

所以它是一颗钻石。现在我们可以把

A.type = 00
B.type = 01
C.type = 10
D.type = 11

右侧有二进制格式的整数。比较按位定义：

(X <= Y) if and only if (n-th bit of X <= n-th bit of Y for all n)

所以我想可以使用这样的排序，问题是如何从给定的图中构造值？我什至不确定解决方案是否始终存在。有什么提示吗？

更新：由于对我使用的术语存在一些误解，让我更明确地说：我对有向无环图感兴趣，这样只有一个节点没有前驱（也称为根），并且任何两个节点之间最多有一个箭头节点。钻石就是一个例子。它不必有一个叶子（即没有后继的节点）。每个节点可能有多个前驱节点和多个后继节点。您可能会说这是一个具有最小元素（即唯一的全局最小元素）的偏序集合。

Answer 1

对于任何 DAG，您可以定义 x <= y为“有一条从 x 到 y 的路径”。这种关系是偏序关系。我认为问题是如何有效地表示这种关系。

\n\n

对于每个顶点 X，定义 \xc2\xa1X 为从 X （包括 X 本身）可到达的顶点集。两种说法

\n\n

\n
• \xc2\xa1X 是 \xc2\xa1Y 的子集
\n
• 从 Y 可以到达 X
\n

\n\n

是等价的。

\n\n

将这些集合编码为位集（N 位二进制数），然后就完成了。

\n