消除“图”中节点的有效算法？

Question

假设我有一个2^N - 1节点的图，编号为1到2^N -1。节点i“依赖”节点j，如果j的二进制表示中的所有位都是1，则在I的二进制表示中也是1。例如，如果N=3，那么节点7依赖于所有其他节点。节点6取决于节点4和节点2。

问题是消除节点。如果没有其他节点依赖，我可以消除一个节点。没有节点依赖于7，所以我可以消除7。在消除7之后，我可以消除6、5和3等等。我想要的是找到一个高效的算法来列出所有可能的唯一消除路径。(也就是说，7-6-5和7-5-6是一样的，所以我们只需要列出其中的一个)。我已经有了一个愚蠢的算法，但我认为一定有更好的方法。

我有三个相关的问题：

1. 这个问题有通称吗？
2. 解决这个问题的最好方法是什么？
3. 是否有唯一消除路径数的一般公式？

编辑:我应该指出，从定义上来说，节点不能依赖自身。

Edit2:让S = {s_1, s_2, s_3,...,s_m}成为所有m有效消除路径的集合。s_i和s_j是“等价的”(就我的目的而言)，当且仅当s_i和s_j在消除后会导致相同的图。我想说得更清楚一点，我想要的是由有效消除步骤产生的所有唯一图的集合。

Edit3:注意消除路径可能有不同的长度。对于N=2，5个有效的消除路径是(),(3),(3,2),(3,1),(3,2,1)。对于N=3，有19条唯一的路径。

Edit4: Re:我的应用程序-应用程序在统计中。给定N个因素，统计模型中有2^N -1可能的项(见影响因素)，它可以包含主要影响(单独的因素)和各种(2,3，.(方法)各因素之间的相互作用。但是，只有当所有子相互作用(或主要影响)都存在时，交互作用才能出现在模型中。例如，对于三个因素a、b和c，只有当所有组成的双向相互作用(a:b、a:c、b:c)都存在时才能存在三元相互作用a:b:c (同样也适用于双向交互)。因此，不允许使用a + b + c + a:b + a:b:c模型。我正在寻找一种快速生成所有有效模型的方法。

Answer 1

多亏了@福克兰Hüffner的回答，我看到我想要做的相当于为N个参数寻找单调的布尔函数。如果您查看维基百科页面上的Dedekind (数)图，该数字以图形的方式表示问题。提出了一种生成单调布尔函数(http://www.mathpages.com/home/kmath094.htm)的算法，该算法构造简单。

出于我的目的，我使用该算法，然后删除生成的二进制数组的第一列和最后一行。从上一行开始，如果可以消除1第四节点，则每一行在i第四列中都有一个i。

谢谢!

Answer 2

从集合的角度来考虑这一点似乎比较容易:您正在寻找{1，.，N}的子集族，这样，对于这个家族中的每个集合，它的所有子集都是存在的。每个这样的家族都是由包含性极大集决定的，它必须是重叠的。成对重叠集的族称为Sperner家族。所以你在寻找Sperner家族，再加上家庭中所有子集的结合。通常情况下，枚举Sperner家族或反密码的已知算法是有用的；如果不知道实际要对它们做什么，就很难说了。

Answer 3

您可以构建一个“堆”，其中深度上的X是在二进制表示中具有X零的所有节点。

然后，从底层开始，将每个项目连接到上面一层的随机父级，直到得到一个单一的组件图。

注意，这个图是一个树，也就是说，除了根节点之外，每个节点都有一个父节点。

然后遍历树(从根开始)并计算其中的路径总数。

更新：

上面的方法是不好的，因为您不能只是为给定的项目选择一个随机的父项--您有有限的项目可以从中选择一个“合法”的父级.但是我把这个方法留在这里，让其他人发表他们的意见(也许不是“那么糟糕”)。

在任何情况下，你为什么不拿出你的图，提取一个生成树(你可以使用Prim算法或Kruskal算法来寻找最小生成树)，然后计算其中的路径数？