假设我有一个由2 ^ N-1个节点组成的图，编号为1到2 ^ N-1。如果二进制表示中j的所有位为1，则节点i“依赖于”节点j。在这种情况下，例如，如果N = 3，则节点7依赖于所有其他节点。节点6依赖于节点4和2。
问题是消除节点。如果没有其他节点依赖它，则可以消除节点。没有节点依赖于7;因此我可以消除7。消除7后，我可以消除6、5和3等。我想找到一种有效的算法来列出所有可能的唯一消除路径。（也就是说，7-6-5与7-5-6相同，因此我们只需要列出其中之一）。我已经有了一个愚蠢的算法，但我认为一定有更好的方法。
我有三个相关的问题：
1. 这个问题有通用名称吗？ 2. 解决这个问题的最佳方法是什么？ 3. 是否有唯一消除路径数量的通式？
编辑：应注意，根据定义，一个节点不能依赖于其本身。
编辑2：让S = {s_1，s_2，s_3，...，s_m}成为所有m个有效消除路径的集合。对于我的目的，s_i和s_j是“等价的”，如果两个消除s_i和s_j将导致相同的图形。我认为要更清楚，我可以说我想要的是所有唯一图形的集合，这些图形是通过有效的消除步骤得出的。
编辑3：注意，消除路径可能具有不同的长度。对于N = 2，5个有效的消除路径为（），（3），（3,2），（3,1）和（3,2,1）。对于N = 3，有19个唯一路径。
问题是消除节点。如果没有其他节点依赖它，则可以消除节点。没有节点依赖于7;因此我可以消除7。消除7后，我可以消除6、5和3等。我想找到一种有效的算法来列出所有可能的唯一消除路径。（也就是说，7-6-5与7-5-6相同，因此我们只需要列出其中之一）。我已经有了一个愚蠢的算法，但我认为一定有更好的方法。
我有三个相关的问题：
1. 这个问题有通用名称吗？ 2. 解决这个问题的最佳方法是什么？ 3. 是否有唯一消除路径数量的通式？
编辑：应注意，根据定义，一个节点不能依赖于其本身。
编辑2：让S = {s_1，s_2，s_3，...，s_m}成为所有m个有效消除路径的集合。对于我的目的，s_i和s_j是“等价的”，如果两个消除s_i和s_j将导致相同的图形。我认为要更清楚，我可以说我想要的是所有唯一图形的集合，这些图形是通过有效的消除步骤得出的。
编辑3：注意，消除路径可能具有不同的长度。对于N = 2，5个有效的消除路径为（），（3），（3,2），（3,1）和（3,2,1）。对于N = 3，有19个唯一路径。
编辑4：关于我的应用程序 - 该应用程序是与统计学相关的。给定N个因素，统计模型中可能包含2^N-1个可能项（参见http://en.wikipedia.org/wiki/Analysis_of_variance#ANOVA_for_multiple_factors），这些可能项可以包含主效应（仅因素）和因素之间的各种（2,3,...方式）交互作用。但是，只有在所有子交互作用（或主效应）存在时，才能在模型中出现交互作用。例如，对于三个因素a、b和c，3路交互作用a:b:c只能在所有组成的二路交互作用（a:b、a:c、b:c）都存在时才能存在（两路也是如此）。因此，模型a+b+c+a:b+a:b:c将不被允许。我正在寻找一种快速生成所有有效模型的方法。
7-6-5和7-5-6是相同的，那么为什么 (虚构路径)7-6-5-4-3-2-1和7-6-4-5-3-1-2不是相同的呢？ - ShahbazN=7的例子，你能否命名任何与7-6-5-4-3-2-1不等价的路径？也许如果你能快速画几个图会更清楚。 - Shahbaz